Abstract
Let r ⩾ 3, n ⩾ r and π = (d 1, d 2, …, d n ) be a graphic sequence. If there exists a simple graph G on n vertices having degree sequence π such that G contains C r (a cycle of length r) as a subgraph, then π is said to be potentially C r -graphic. Li and Yin (2004) posed the following problem: characterize π = (d 1, d 2, …, d n ) such that π is potentially C r -graphic for r ⩾ 3 and n ⩾ r. Rao and Rao (1972) and Kundu (1973) answered this problem for the case of n = r. In this paper, this problem is solved completely.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bollobás B. Extremal Graph Theory. London: Academic Press, 1978
Erdős P, Gallai T. Graphs with given degrees of vertices. Math Lapok, 1960, 11: 264–274
Erdős P, Jacobson M S, Lehel J. Graphs realizing the same degree sequences and their respective clique numbers. In: Alavi Y, et al. eds. Graph Theory, Combinatorics and Applications, vol. 1. New York: John Wiley & Sons, 1991, 439–449
Gould R J, Jacobson M S, Lehel J. Potentially G-graphical degree sequences. In: Alavi Y, et al. eds. Combinatorics, Graph Theory, and Algorithms, vol. 1. Kalamazoo, Michigan: New Issues Press, 1999, 451–460
Kézdy A E, Lehel J. Degree sequences of graphs with prescribed clique size. In: Alavi Y, et al. eds. Combinatorics, Graph Theory, and Algorithms vol. 2. Kalamazoo, Michigan: New Issues Press, 1999, 535–544
Kleitman D J, Wang D L. Algorithm for constructing graphs and digraphs with given valences and factors. Discrete Math, 1973, 6: 79–88
Kundu S. The k-factor conjecture is true. Discrete Math, 1973, 6: 367–376
Li J S, Song Z X. The smallest degree sum that yields potentially P k-graphic sequences. J Graph Theory, 1998, 29: 63–72
Li J S, Song Z X. An extremal problem on the potentially P k-graphic sequence. Discrete Math, 2000, 212: 223–231
Li J S, Song Z X, Luo R. The Erdős-Jacobson-Lehel conjecture on potentially Pk-graphic sequences is true. Sci China Ser A, 1998, 41: 510–520
Li J S, Yin J H. Extremal graph theory and degree sequences (in Chinese). Adv Math (China), 2004, 33: 273–283
Li J S, Yin J H. The threshold for the Erdős, Jacobson and Lehel conjecture to be true. Acta Math Sin (Engl Ser), 2006, 22: 1133–1138
Rao A R. An Erdős-Gallai type result on the clique number of a realization of a degree sequence. Unpublished
Rao A R, Rao S B. On factorable degree sequences. J Combin Theory Ser B, 1972, 13: 185–191
Yin J H, Li J S. The smallest degree sum that yields potentially K r,r-graphic sequences. Sci China Ser A, 2002, 45: 694–705
Yin J H, Li J S. An extremal problem on potentially K r,s-graphic sequences. Discrete Math, 2003, 260: 295–305
Yin J H, Li J S. Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size. Discrete Math, 2005, 301: 218–227
Yin J H, Li J S, Chen G L. A variation of a classical Turán-type extremal problem. European J Combin, 2004, 25: 989–1002
Yin J H, Li J S, Chen G L. The smallest degree sum that yields potentially K 2,s -graphic sequences. Ars Combin, 2005, 74: 213–222
Yin J H, Wang Y. A characterization for a graphic sequence to have a realization containing a desired cycle. Utilitas Math, to appear, 2010
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Yin, J. A characterization for a graphic sequence to be potentially C r -graphic. Sci. China Math. 53, 2893–2905 (2010). https://doi.org/10.1007/s11425-010-3124-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11425-010-3124-6