An extremal problem on potentially K_m-P_k-graphic sequences

2004/09/24 by Chunhui Lai, Lai, Chunhui
Computer Science · Mathematics · #05C07 #05C35 #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #math.CO #msc:05C07 #msc:05C35

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

5 pages

openalex publication_date 2004/09/24 · arxiv created 2006/07/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A sequence S is potentially K_m-P_k graphical if it has a realization containing a K_m-P_k as a subgraph. Let σ(K_m-P_k, n) denote the smallest degree sum such that every n-term graphical sequence S with σ(S)≥ σ(K_m-P_k, n) is potentially K_m-P_k graphical. In this paper, we prove that σ(K_m-P_k, n)≥ (2m-6)n-(m-3)(m-2)+2, for n ≥ m ≥ k+1≥ 4. We conjecture that equality holds for n ≥ m ≥ k+1≥ 4. We prove that this conjecture is true for m=k+1=5 and m=k+2=5.

Related

• An extremal problem on potentially K_p₁,p₂,...,p_t-graphic sequences
• A note on potentially K₄-e graphical sequences
• The smallest degree sum that yields potentially C_k-graphical sequence
• The smallest degree sum that yields potentially K_r+1-Z-graphical Sequences
• A Characterization On Potentially K₆-C₄-graphic Sequences