An Extremal Problem On Potentially Kr+1-H-graphic Sequences

作者：Lai Chunhui^*; Hu Lili

来源：Ars Combinatoria, 2010, 94: 289-298.

• graph
• degree sequence
• potentially K(r 1) - H-graphic sequence

Let K(k), C(k), T(k), and P(k) denote a complete graph on k vertices, a cycle on k vertices, a tree on k + 1 vertices, and a path on k + 1 vertices, respectively. Let K(m) - H be the graph obtained from K(m) by removing the edges set E(H) of the graph H (H is a subgraph of K(m)). A sequence S is potentially K(m) - H-graphical if it has a realization containing a K(m) - H as a subgraph. Let sigma(K(m) - H, n) denote the smallest degree sum such that every n-term graphical sequence S with sigma(S) >= sigma(K(m) - H, n) is potentially K(m) - H-graphical. In this paper, we determine the values of sigma(K(r+1) -H, n) for n >= 4r + 10, r >= 3, r + 1 >= k >= 4 where H is a graph on k vertices which contains a tree on 4 vertices but not contains a cycle on 3 vertices. We also determine the values of a (K(r+1) - P(2), n) for n >= 4r + 8, r >= 3.

• 出版日期2010-1
• 单位闽南师范大学