pith. sign in

arxiv: math/0408292 · v2 · submitted 2004-08-22 · 🧮 math.CO

An extremal problem on potentially K_(p,1,1)-graphic sequences

classification 🧮 math.CO
keywords sigmagraphicalpotentiallyconjectureprovesequencecompletecontaining
0
0 comments X
read the original abstract

A sequence $S$ is potentially $K_{p,1,1}$ graphical if it has a realization containing a $K_{p,1,1}$ as a subgraph, where $K_{p,1,1}$ is a complete 3-partite graph with partition sizes $p,1,1$. Let $\sigma(K_{p,1,1}, n)$ denote the smallest degree sum such that every $n$-term graphical sequence $S$ with $\sigma(S)\geq \sigma(K_{p,1,1}, n)$ is potentially $K_{p,1,1}$ graphical. In this paper, we prove that $\sigma (K_{p,1,1}, n)\geq 2[((p+1)(n-1)+2)/2]$ for $n \geq p+2.$ We conjecture that equality holds for $n \geq 2p+4.$ We prove that this conjecture is true for $p=3$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.