Abstract
Erdös and Sós conjectured in 1963 that every graph G on n vertices with edge number e(G) > ½ (k − 1)n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n ≥ 9/2 k 2 + 37/2 k+14 and every graph G on n vertices with e(G) > ½ (k − 1)n, we prove that there exists a graph G′ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Gould, R. J., Jacobson, M. S., Lehel, J.: Potentially G-graphical degree sequences, in: Y. Alavi et al., (Eds.), Combinatorics, Graph Theory, and Algorithms, Vol.1, New Issues Press, Kalamazoo Michigan, 1999, 451–460
Erdös, P., Jacobson, M. S., Lehel, J.: Graphs realizing the same degree sequences and their respective clique numbers, in: Y. Alavi et al., (Eds.), Graph Theory, Combinatorics and Applications, Vol.1, John Wiley & Sons, New York, 1991, 439–449
Li, J. S., Song, Z. X.: An extremal problem on the potentially P k-graphic sequence. Discrete Math., 212, 223–231 (2000)
Li, J. S., Song, Z. X.: The smallest degree sum that yields potentially P k-graphic sequences. J. Graph Theory, 29, 63–72 (1998)
Li, J. S., Song, Z. X., Luo, R.: The Erdös-Jacobson-Lehel conjecture on potentially P k-graphic sequences is true. Sci. China Ser.A, 41, 510–520 (1998)
Li, J. S., Yin, J. H.: The threshold for the Erdös, Jacobson and Lehel conjecture to be true. Acta Mathematica Sinica, English Series, 22, 1133–1138 (2006)
Erdös, P., Gallai, T.: On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hangar, 10, 337–356 (1959)
Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications, The Macmillan Press, London, 1976
Woźniak, M.: On the Erdös-Sós conjecture. J. Graph Theory, 21, 229–234 (1996)
Brandt, S., Dobson, E.: The Erdös-Sós conjecture for graphs of girth 5. Discrete Math., 150, 411–414 (1996)
Saclé, J. F., Woźniak, M.: The Erdös-Sós conjecture for graphs without C 4. J. Combin. Theory Ser. B, 70, 367–372 (1997)
Wang, M., Li, G. J., Liu, A. D.: A result of Erdös-Sós conjecture. Ars Combinatoria, 55, 123–127 (2000)
Yin, J. H., Li, J. S.: The Erdös-Sós conjecture for graphs whose complements contain no C 4. Acta Math. Appl. Sin. Eng. Ser., 20, 397–400 (2004)
Wang, M., Zhao, Y. Q., Li, G. J.: A new result on Erdös-Sós conjecture. Acta Math. Sci., 17, 125–131 (1997)
Kleitman, D. J., Wang, D. L.: Algorithm for constructing graphs and digraphs with given valences and factors. Discrete Math., 6, 79–88 (1973)
Erdös, P., Gallai, T.: Graphs with given degrees of vertices. Math. Lapok, 11, 264–274 (1960)
Yin, J. H., Li, J. S.: An extremal problem on potentially K r,s-graphic sequences. Discrete Math., 260, 295–305 (2003)
Yin, J. H., Li, J. S.: Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size. Discrete Math., 301, 218–227 (2005)
Li, J. S., Song, Z. X.: On the potentially P k-graphic sequence. Discrete Math., 195, 255–262 (1999)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by National Natural Science Foundation of China (Nos. 10861006, 10401010)
Rights and permissions
About this article
Cite this article
Yin, J.H., Li, J.S. A variation of a conjecture due to Erdös and Sós. Acta. Math. Sin.-English Ser. 25, 795–802 (2009). https://doi.org/10.1007/s10114-009-7260-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10114-009-7260-2