Potentially K-1,K-1,(t)-graphic sequences

作者：Yin, Jian-Hua^*; Li, Jiong-Sheng; Li, Wen-Ya

来源：Ars Combinatoria, 2012, 104: 481-488.

• graph
• degree sequence
• potentially K-1,K-1,K-t-graphic sequence

Let sigma(K-1,K-1,K-t,n) be the smallest even integer such that every n-term graphic sequence pi r = (d(1), d(2), ... , d(n)) with sigma(pi) = d(1) + d(2) + ... + d(n) >= sigma(K-1,K-1,K-t,n) has a realization G containing K-1,K-1,K-t as a subgraph, where K1,1,t is the 1 x 1 x t complete 3-partite graph. Recently, Lai (Discrete Mathematics and Theoretical Computer Science, 7(2005), 7581) conjectured that for n >= 2t + 4, @@@ sigma(K-1,K-1,K-t,K- n) = {(t + 1)(n - 1) + 2 if n is odd or t is odd, (t + 1)(n - 1) + 1 if n and t are even. @@@ In this paper, we prove that the above equality holds for n >= t + 4.

• 出版日期2012-4
• 单位中国科学技术大学; 海南大学