×

Gaps in the saturation spectrum of trees. (English) Zbl 1401.05158

Summary: 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 \(\operatorname{sat}(n,H)\), while the maximum size is the well studied extremal number, \(\operatorname{ex}(n,H)\). The saturation spectrum for a graph \(H\) is the set of sizes of \(H\)-saturated graphs between \(\operatorname{sat}(n,H)\) and \(\operatorname{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.

MSC:

05C35 Extremal problems in graph theory
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[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: · Zbl 1291.05095
[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: · Zbl 0821.05031
[3] G.A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc. s3-2 (1952) 69-81. doi: · Zbl 0047.17001
[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. · Zbl 0178.27301
[6] P.Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959) 337-356. · Zbl 0090.39401
[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: · Zbl 1246.05117
[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: · Zbl 1068.05035
[11] A.F. Sidorenko, Asymptotic solution for a new class of forbidden r-graphs, Combi- natorica 9 (1989) 207-215. doi: · Zbl 0732.05031
[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:
[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:
[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:
[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:
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.