A generalization of a conjecture due to Erdős, Jacobson and Lehel

AbstractAn 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 r-graphic if it is realizable by an r-graph on n vertices. Let σ(Km+1(r),n) be the smallest even integer such that each n-term r-graphic sequence with term sum of at least σ(Km+1(r),n) is realizable by an r-graph containing Km+1(r) as a subgraph. In this paper, we determine the value of σ(Km+1(r),n) for sufficiently large n, which generalizes a conjecture due to Erdős, Jacobson and Lehel