A note on the characterization of potentially Kr+1 - P-k-graphic Sequences

作者：Hu Lili^*

来源：Utilitas Mathematica, 2014, 93: 291-303.

• graph
• degree sequence
• potentially A(r+1) - P-k-graphic sequences
• potentially Kr+1 - P-k-graphic sequences

For given a graph H, a graphic sequence pi = (d(1), d(2), ..., d(n)) is said to be potentially H-graphic if there exists a realization of pi containing H as a subgraph. Let P-k denote a path on k + 1 vertices and Kr-1-P-k (1 <= k <= r) be the graph obtained from Kr+1 by removing the k edges of P-k. If a graphic sequence pi = (d(1), d(2), ..., d(n)) has a realization G with the vertex set V(G) {v(1), v(2), ..., v(n)} such that d(G)(v(i)) = d(i) for 1 <= i <= n and G[{v(1), v(2), ..., v(r+1)}] = Kr+1-Pk(1 <= k <= r) such that d(Kr+1)-P-k (v(i)) = r for 1 <= i < r-k, d(Kr+1)-P-k (v(i)) = r - 1 for r - k + 1 <= i <= r - k + 2 and d(Kr+1)-P-k, (v(i)) = r - 2 for r-k+3 <= i <= r+1, then pi is said to be potentially A(r+1)-P-k-graphic. In this paper, we first characterize the potentially A(r+1)-P-k-graphic sequences which is analogous to Wang-Yin characterization [13] using a system of inequalities. Then we obtain a sufficient and necessary condition for a graphic sequence pi to have a realization containing Kr+1-P-k as an induced subgraph. Moreover, we characterize potentially Kr+1-P-4-graphic sequences.

• 出版日期2014-3
• 单位闽南师范大学