A note on potentially K₄-e graphical sequences

2003/08/11 by Chunhui Lai
Mathematics · #math.CO #msc:05C07 #msc:05C35

paper · pdf

published as Australasian Journal of Combinatorics, 24(2001), 123-127 · 5 pages

arxiv created 2003/08/11 · arxiv updated 2009/12/01

Abstract

A sequence S is potentially K₄-e graphical if it has a realization containing a K₄-e as a subgraph. Let σ(K₄-e, n) denote the smallest degree sum such that every n-term graphical sequence S with σ(S)≥ σ(K₄-e, n) is potentially K₄-e graphical. Gould, Jacobson, Lehel raised the problem of determining the value of σ(K₄-e, n). In this paper, we prove that σ(K₄-e, n)=2[(3n-1)/2] for n≥ 7, and n=4,5, and σ(K₄-e, 6)= 20.

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
• A Characterization On Potentially K₆-C₄-graphic Sequences
• The smallest degree sum that yields potentially C_k-graphical sequence
• On Potentially (K₅-C₄)-graphic Sequences