一个实现包含圈C3,...,Cl可图序列问题的渐近解

李光明, 尹建华

数学学报 ›› 2021, Vol. 64 ›› Issue (3) : 443-454.

PDF(564 KB)
PDF(564 KB)
数学学报 ›› 2021, Vol. 64 ›› Issue (3) : 443-454. DOI: 10.12386/A2021sxxb0037
论文

一个实现包含圈C3,...,Cl可图序列问题的渐近解

    李光明, 尹建华
作者信息 +

Asymptotic Solution to a Problem about Graphic Sequences with a Realization Containing Cycles C3,..., Cl

    Guang Ming LI, Jian Hua YIN
Author information +
文章历史 +

摘要

一个非增的非负整数序列π=(d1,...,dn)称为是可图的如果它是一个n个顶点的简单图G的度序列.一个可图序列π=(d1,...,dn)称为是蕴含3Cl-可图的如果π有一个实现包含每一个长为r的圈,其中3 ≤ rl.众所周知,如果一个关于l个顶点的图G的非增的度序列(d1,...,dl)满足Pósa条件,即如果对于每一个i,1 ≤ i < l/2,有di+1-ii+1,则G是泛圈的或者是二部的.在本文中,我们得到了一个蕴含3Cl-可图序列的Pósa-型条件,即证明如果l ≥ 5是一个整数,nlπ=(d1,...,dn)是一个可图序列满足对于每一个i,1 ≤ i < l/2,有di+1-ii+1,则π是蕴含3Cl-可图的.我们也证明了这个结果是Li等人[Adv.Math.(China),2004,33(3):273-283]一个问题的渐近解.作为应用,我们也证明了此结果完全包含了Lai[J.Combin.Math.Combin.Comput.,2004,49:57-64]对于l ≥ 5且nlσCln)之值.

Abstract

A non-increasing sequence π=(d1,...,dn of nonnegative integers is said to be graphic if it is realizable by a simple graph G on n vertices. A graphic sequence π=(d1,...,dn is said to be potentially 3Cl-graphic if there is a realization of π containing cycles of every length r, 3 ≤ rl. It is well-known that if the nonincreasing degree sequence (d1,..., dl) of a graph G on l vertices satisfies the Pósa condition that dl +1-ii + 1 for every i with 1 ≤ i < l/2, then G is either pancyclic or bipartite. In this paper, we obtain a Pósa-type condition of potentially 3Cl-graphic sequences, that is, we prove that if l ≥ 5 is an integer, nl and π=(d1,...,dn is a graphic sequence with dl +1-ii + 1 for every i with 1 ≤ i < l/2, then π is potentially 3Cl-graphic. We show that this result is an asymptotic solution to a problem due to Li et al.[Adv. Math. (China), 2004, 33(3):273-283]. As an application, we also show that this result completely implies the value σ(Cl, n) for l ≥ 5 and nl due to Lai[J. Combin. Math. Combin. Comput., 2004, 49:57-64].

关键词

可图序列 / 实现 / 蕴含3Cl-可图序列

Key words

graphic sequence / realization / potentially 3Cl-graphic sequence

引用本文

导出引用
李光明, 尹建华. 一个实现包含圈C3,...,Cl可图序列问题的渐近解. 数学学报, 2021, 64(3): 443-454 https://doi.org/10.12386/A2021sxxb0037
Guang Ming LI, Jian Hua YIN. Asymptotic Solution to a Problem about Graphic Sequences with a Realization Containing Cycles C3,..., Cl. Acta Mathematica Sinica, Chinese Series, 2021, 64(3): 443-454 https://doi.org/10.12386/A2021sxxb0037

参考文献

[1] Bondy J. A., Murty U. S. R., Graph Theory with Applications, North-Holland, New York, 1976.
[2] Chen G., Fan Y. M., Yin J. H., On potentially 3C6-graphic sequences, J. Guangxi Normal Univ. (Nat. Sci. Ed.), 2006, 24(3):26-29.
[3] Erd?s P., Gallai T., Graphs with prescribed degrees of vertices (Hungarian), Mat. Lapok, 1960, 11:264-274.
[4] Gould R. J., Jacobson M. S., Lehel J., Potentially G-graphical degree sequences, in:Y. Alavi et al., (Eds.), Combinatorics, Graph Theory, and Algorithms, New Issues Press, Kalamazoo Michigan, 1999:451-460.
[5] Kleitman D. J., Wang D. L., Algorithm for constructing graphs and digraphs with given valences and factors, Discrete Math., 1973, 6:79-88.
[6] Lai C. H., The smallest degree sum that yields potentially Ck-graphical sequences, J. Combin. Math. Combin. Comput., 2004, 49:57-64.
[7] Li J. S., Yin J. H., Extremal graph theory and degree sequences (Chinese), Adv. Math. (China), 2004, 33(3):273-283.
[8] Nash-Williams C. St. J. A., Valency sequences which force graphs to have hamiltonian circuits, Interim report, University of Waterloo, Waterloo, 1970.
[9] Schmeichel E. F., Hakimi S. L., Pancyclic graphs and a conjecture of Bondy and Chvátal, J. Combin. Theory (B), 1974, 17:22-34.
[10] Yin J. H., A characterization for a graphic sequence to be potentially Cr-graphic, Sci. China Math., 2010, 53(11):2893-2905.
[11] Yin J. H., Chen G., Chen G. L., On potentially kCl-graphic sequences, J. Combin. Math. Combin. Comput., 2007, 61:141-148.
[12] Yin J. H., Ye K., Li J. Y., Graphic sequences with a realization containing cycles C3,..., Cl, Appl. Math. Comput., 2019, 353:88-94.

基金

海南省自然科学基金高层次人才资助项目(2019RC085);国家自然科学基金资助项目(11961019)

PDF(564 KB)

469

Accesses

0

Citation

Detail

段落导航
相关文章

/