Geodesic
Gaps in the Saturation Spectrum of Trees
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 157-170.

Voir la notice de l'article provenant de la source Library of Science

A graph G is H-saturated if H is not a subgraph of G but the addition of any edge from the complement of G to G results in a copy of H. The minimum number of edges (the size) of an H-saturated graph on n vertices is denoted sat(n,H), while the maximum size is the well studied extremal number, ex(n,H). The saturation spectrum for a graph H is the set of sizes of H-saturated graphs between sat(n,H) and ex(n,H). In this paper we show that paths, trees with a vertex adjacent to many leaves, and brooms have a gap in the saturation spectrum.
Keywords: saturation spectrum, tree, saturation number 
@article{DMGT_2019_39_1_a12,
     author = {Horn, Paul and Gould, Ronald J. and Jacobson, Michael S. and Thomas, Brent J.},
     title = {Gaps in the {Saturation} {Spectrum} of {Trees}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {157--170},
     publisher = {mathdoc},
     volume = {39},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a12/}
}
TY  - JOUR
AU  - Horn, Paul
AU  - Gould, Ronald J.
AU  - Jacobson, Michael S.
AU  - Thomas, Brent J.
TI  - Gaps in the Saturation Spectrum of Trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 157
EP  - 170
VL  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a12/
LA  - en
ID  - DMGT_2019_39_1_a12
ER  - 
%0 Journal Article
%A Horn, Paul
%A Gould, Ronald J.
%A Jacobson, Michael S.
%A Thomas, Brent J.
%T Gaps in the Saturation Spectrum of Trees
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 157-170
%V 39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a12/
%G en
%F DMGT_2019_39_1_a12
Horn, Paul; Gould, Ronald J.; Jacobson, Michael S.; Thomas, Brent J. Gaps in the Saturation Spectrum of Trees. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 157-170. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a12/

[1] K. Amin, J. Faudree, R.J. Gould and E. Sidorowicz, On the non-(p − 1)-partite Kp-free graphs, Discuss. Math. Graph Theory 33 (2013) 9-23. doi: 10.7151/dmgt.1654

[2] C. Barefoot, K. Casey, D. Fisher, K. Fraughnaugh and F. Harary, Size in maximal triangle-free graphs and minimal graphs of diameter 2, Discrete Math. 138 (1995) 93-99. doi: 10.1016/0012-365X(94)00190-T

[3] G.A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc. s3-2 (1952) 69-81. doi: 10.1112/plms/s3-2.1.69

[4] P. Erdős, Extremal problems in graph theory, in: Proc. Sympos. Smolenice 13 (1963) 29-36.

[5] P. Erdős, and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1965) 51-57.

[6] P.Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959) 337-356.

[7] J. Faudree, R.J. Gould, M. Jacobson and B. Thomas, Saturation spectrum for brooms, manuscript.

[8] R.J. Gould, W. Tang, E. Wei and C. Zhang, The edge spectrum of the saturation number for small paths, Discrete Math. 312 (2012) 2682-2689. doi: 10.1016/j.disc.2012.01.012

[9] W. Mantel, Problem 28, Wiskundige Opgaven 10 (1907) 60-61.

[10] A. McLennan, The Erdős-Sόs conjecture for trees of diameter four, J. Graph Theory 49 (2005) 291-301. doi: 10.1002/jgt.20083

[11] A.F. Sidorenko, Asymptotic solution for a new class of forbidden r-graphs, Combi- natorica 9 (1989) 207-215. doi: 10.1007/BF02124681

[12] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436-452, in Hungarian.

[13] A. Doǧan, On Saturated Graphs and Combinatorial Games (University of Memphis, 2016).

[14] J. Hladký, J. Komlόs, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlόs-Sόs Conjecture I: The sparse decomposition, SIAM J. Discrete Math. 31 (2017) 945-982. doi: 10.1137/140982842

[15] J.Hladký, J. Komlόs, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlόs-Sόs Conjecture II: The rough structure of LKS graphs, SIAM J. Discrete Math. 31 (2017) 983-1016. doi: 10.1137/140982854

[16] J.Hladký, J. Komlόs, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlόs-Sόs Conjecture III: The finer structure of LKS graphs, SIAM J. Discrete Math. 31 (2017) 1017-1071. doi: 10.1137/140982866

[17] J. Hladký, J. Komlόs, D. Piguet, M. Simonovits, M. Stein, M. and E. Szemerédi, The approximate Loebl-Komlόs-Sόs Conjecture IV: Embedding techniques and the proof of the main result, SIAM J. Discrete Math. 31 (2017) 1072-1148. doi: 10.1137/140982878.