A Collection of Minimally Path Square-Saturated Graphs
DOI:
https://doi.org/10.15575/kubik.v5i1.8415Keywords:
power graphs, path square, saturated numbers, saturated graphs, degree sequence of graphAbstract
Given a simple graph G, m a positive integer. The square of path graph P_m, denoted by P_m^2, is a graph obtained from P_m by adding new edges between any pair of vertices at distance at most 2 in P_m. A graph G is P_m^2-saturated if G does not contain P_m^2 as a subgraph, but the addition of any edge between two nonadjacent vertices in G contain P_m^2. The minimum size of P_m^2-saturated graph on n vertices is called a saturation number for P_m^2, denoted by sat(n,P_m^2). A set Sat(n,P_m^2 )={G:|V(G)|=sat(n,P_m^2) and G a P_m^2-saturated graph}. All graphs in Sat(n,P_m^2) are obtained computationally for n≤8 and m≤8 and expressed by their degree sequence.
References
W. Mantel, "Problem 28," Wiskundige Opgaven, vol. 10, pp. 60-61, 1907.
P. Erdős and T. Gallai, "On the minimal number of vertices representing the edges of graph.," Magyar tud. Akad. Mat. Kutato Int. Kozl., vol. 6, pp. 181-203, 1961.
P. Erdős, A. Hajnal and J. W. Moon, "A problem in graph theory," Amer. Math. Monthly, vol. 71, pp. 1107-1110, 1964.
P. Turán, "Eine Extremalaufgabe aus der Graphentheorie," Mat. Fiz. Lapok, vol. 48, no. 1941, pp. 436-452, 1941.
Downloads
Published
2020-10-05
How to Cite
Nursyahida, S. (2020). A Collection of Minimally Path Square-Saturated Graphs. KUBIK: Jurnal Publikasi Ilmiah Matematika, 5(1), 20–27. https://doi.org/10.15575/kubik.v5i1.8415
Issue
Section
Articles
Citation Check
License
Authors who publish in KUBIK: Jurnal Publikasi Ilmiah Matematika agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Â
Â
