An extremal problem on potentially K-p,K-1,K-1-graphic sequences
A sequence S is potentially K-p,K-1,K-1 graphical if it has a realization containing a K-p,K-1,K-1 as a subgraph, where K-p,K-1,K-1 is a complete 3-partite graph with partition sizes p, 1, 1. Let sigma(K-p,K- 1,K-1, n) denote the smallest degree sum such that every n-term graphical sequence S with sigma( S) >= sigma(K-p,K- 1,K-1, n) is potentially K-p,K-1,K-1 graphical. In this paper, we prove that sigma(K-p,K-1,K-1, n) >= 2[((p + 1)(n - 1) + 2)/2] for n >= p + 2. We conjecture that equality holds for n >= 2p + 4. We prove that this conjecture is true for p = 3.
graph degree sequence potentially kp,1,1-graphic sequence