r-可图序列与r-完全子图

尹建华

数学学报 ›› 2013, Vol. 56 ›› Issue (3) : 369-380.

PDF(461 KB)
PDF(461 KB)
数学学报 ›› 2013, Vol. 56 ›› Issue (3) : 369-380. DOI: 10.12386/A2013sxxb0036
论文

r-可图序列与r-完全子图

    尹建华
作者信息 +

r-Graphic Sequences and r-Complete Subgraphs

    Jian Hua YIN
Author information +
文章历史 +

摘要

一个r-图是一个无环的无向图,其中任何两个顶点之间至多被r条边连接.一个m+1个顶点的r-完全图, 记为Km+1(r),是一个m+1个顶点的r-图, 其中任何两个顶点之间恰好被r条边连接.一个非增的非负整数序列π=(d1, d2,..., dn)称为是r-可图的如果它是某个n个顶点的r-图的度序列.一个r-可图序列π称为是蕴含(强迫)Km+1(r)-可图的如果π有一个实现包含Km+1(r)作为子图(π的每一个实现包含Km+1(r)作为子图). 设σ(Km+1(r),n)τ (Km+1(r), n))表示最小的偶整数t,使得每一个r-可图序列π=(d1, d2,..., dn)具有∑i=1ndit是蕴含(强迫) Km+1(r)-可图的.易见,σ(Km+1(r),n)是Erdös等人的一个猜想从1-图到r-图的扩充且τ (Km+1(r), n))是经典Turán定理从1-图到r-图的扩充.本文给出了蕴含Km+1(r)r-可图序列的两个简单充分条件.此两个条件包含了Yin和Li在[Discrete Math., 2005, 301:218-227]中的两个主要结果和当n ≥ max{m2+3m+1-[m2+m/r], 2m+1+[m/r]}时,σ(Km+1(r),n)之值. 此外, 我们还确定了当nm+1时,τ (Km+1(r), n))之值.

Abstract

An r-graph is a loopless undirected graph in which no two vertices are joined by more than r edges. An r-complete graph on m+1 vertices, denoted by Km+1(r), is an r-graph on m+1 vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π=(d1, d2,..., dn) of nonnegative integers is said to be r-graphic if it is the degree sequence of some r-graph on n vertices. An r-graphic sequence π is said to be potentially (resp. forcibly) Km+1(r)-graphic if π has a realization containing Km+1(r) as a subgraph (resp. every realization of π contains Km+1(r) as a subgraph). Let σ(Km+1(r), n) (resp. τ (Km+1(r), n)) denote the smallest even integer t such that each r-graphic sequence π=(d1,d2,..., dn) with ∑i=1ndit is potentially (resp. forcibly) Km+1(r)-graphic. Clearly, σ(Km+1(r), n) is an extension from 1-graph to r-graph of a conjecture due to Erdös et al and τ (Km+1(r), n) is an extension from 1-graph to r-graph of the classical Turán's theorem. In this paper, we give two simple sufficient conditions for an r-graphic sequence to be potentially Km+1(r)-graphic, which imply two main results due to Yin and Li (Discrete Math., 2005, 301: 218-227) and the value of σ(Km+1(r), n) for n ≥ max{m2+3m+1-[m2+m/r], 2m+1+[m/r]}. Moreover, we also determine the value of τ(Km+1(r), n) for nm+1.

关键词

r-图 / r-完全图 / r-可图序列

Key words

r-graph / r-complete graph / r-graphic sequence

引用本文

导出引用
尹建华. r-可图序列与r-完全子图. 数学学报, 2013, 56(3): 369-380 https://doi.org/10.12386/A2013sxxb0036
Jian Hua YIN. r-Graphic Sequences and r-Complete Subgraphs. Acta Mathematica Sinica, Chinese Series, 2013, 56(3): 369-380 https://doi.org/10.12386/A2013sxxb0036

参考文献

[1] Chungphaisan V., Conditions for sequences to be r-graphic, Discrete Math., 1974, 7: 31-39.

[2] Yin J. H., A generalization of a conjecture due to Erdös, Jacobson and Lehel, Discrete Math., 2009, 309: 2579-2583.

[3] 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, John Wiley & Sons, New York, 1991, 1: 439-449.

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

[5] 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, 1: 451-460.

[6] Li J. S., Song Z. X., An extremal problem on the potentially Pk-graphic sequence, Discrete Math., 2000, 212: 223-231.

[7] Li J. S., Song Z. X., The smallest degree sum that yields potentially Pk-graphic sequences, J. Graph Theory, 1998, 29: 63-72.

[8] 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.

[9] Mubayi D., Graphic sequence that have a realization with large clique number, J. Graph Theory, 2000, 34: 20-29.

[10] Li J. S., Yin J. H., The threshold for the Erdös, Jacobson and Lehel conjecture to be true, Acta Mathematica Sinica, English Series, 2006, 22: 1133-1138.

[11] 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.

[12] Bondy J. A., Murty U. S. R., Graph Theory with Applications, North-Holland, New York, 1976.

基金

国家自然科学基金资助项目(11161016, 11261015, 10861006)

PDF(461 KB)

Accesses

Citation

Detail

段落导航
相关文章

/