The smallest degree sum that yields potentially C_k-graphical sequence

2002/06/30 by Chunhui Lai
Mathematics · #math.CO #msc:05C07 #msc:05C35

paper · pdf

published as Journal of Combinatorial Mathematics and Combinatorial Computing 49 (2004), 57-64 · 8 pages

arxiv created 2004/08/22 · arxiv updated 2009/11/30

Abstract

In this paper we consider a variation of the classical Turán-type extremal problems. Let S be an n-term graphical sequence, and σ(S) be the sum of the terms in S. Let H be a graph. The problem is to determine the smallest even l such that any n-term graphical sequence S having σ(S)≥ l has a realization containing H as a subgraph. Denote this value l by σ(H, n). We show σ(C_2m+1, n)=m(2n-m-1)+2, for m≥ 3, n≥ 3m; σ(C_2m+2, n)=m(2n-m-1)+4, for m≥ 3, n≥ 5m-2.

Related

• The smallest degree sum that yields potentially K_r+1-Z-graphical Sequences
• An extremal problem on potentially K_m-P_k-graphic sequences
• On the Sum Neccesary to Ensure that a Degree Sequence is Potentially H-Graphic
• A note on potentially K₄-e graphical sequences
• An extremal problem on potentially K_p₁,p₂,...,p_t-graphic sequences