An extremal problem on potentially K_p₁,p₂,...,p_t-graphic sequences

2004/08/24 by Chunhui Lai, Lai, Chunhui
Mathematics · #05C07 #05C35 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C07 #msc:05C35

paper · pdf · doi:10.48550/arxiv.math/0408326

4 pages

arxiv created 2004/08/24 · arxiv updated 2009/12/01

Abstract

A sequence S is potentially K_p₁,p₂,...,p_t graphical if it has a realization containing a K_p₁,p₂,...,p_t as a subgraph, where K_p₁,p₂,...,p_t is a complete t-partite graph with partition sizes p₁,p₂,...,p_t (p₁≥ p₂≥ ...≥ p_t ≥ 1). Let σ(K_p₁,p₂,...,p_t, n) denote the smallest degree sum such that every n-term graphical sequence S with σ(S)≥ σ(K_p₁,p₂,...,p_t, n) is potentially K_p₁,p₂,...,p_t graphical. In this paper, we prove that σ(K_p₁,p₂,...,p_t, n)≥ 2[((2p₁+2p₂+...+2p_t-p₁-p₂-...-p_i-2)n -(p₁+p₂+...+p_t-p_i)(p_i+p_i+1+...+p_t-1)+2)/2] for n ≥ p₁+p₂+...+p_t, i=2,3,...,t.

Related

• An extremal problem on potentially K_m-P_k-graphic sequences
• A note on potentially K₄-e graphical sequences
• The smallest degree sum that yields potentially C_k-graphical sequence
• A Characterization On Potentially K_2,5-graphic Sequences
• The smallest degree sum that yields potentially K_r+1-Z-graphical Sequences