A generalization of a conjecture due to Erdos, Jacobson and Lehel

作者：Yin, Jian-Hua^*

来源：Discrete Mathematics, 2009, 309(8): 2579-2583.

DOI：10.1016/j.disc.2008.04.057

• r-graph
• r-complete graph
• r-graphic sequence

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 K(m+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 pi = (d(1), d(2),...,d(n)) of nonnegative integers is r-graphic if it is realizable by an r-graph on n vertices. Let sigma(K(m+1)((r)), n) be the smallest even integer such that each n-term r-graphic sequence with term sum of at least sigma(K(m+1)((r)), n) is realizable by an r-graph containing K(m+1)((r)) as a subgraph. In this paper, we determine the value of sigma(K(m+1)((r)), n) for, sufficiently large n, which generalizes a conjecture due to Erdos, Jacobson and Lehel.

• 出版日期2009-4-28
• 单位海南大学