A note on potentially $K_4-e$ graphical sequences

Abstract

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

5 pages

Cited by in corpus (6)

• An extremal problem on potentially $K_m-C_4$-graphic sequences
• The smallest degree sum that yields potentially K_{r+1}-Z-graphical Sequences
• Exact solution to an extremal problem on graphic sequences with a realization containing every $2$-tree on $k$ vertices
• Potentially $K_m-G$-graphical Sequences: A Survey
• On potentially $K_{r+1}-U$-graphical Sequences
• An Extremal Problem On Potentially $K_{r+1}-(k{P}_2\bigcup t{K}_2)$-graphic Sequences