A Characterization for a Graphic Sequence to be Potentially \(K_{1^3},4\)-Graphic

Nan Gao1, Meng-xiao Yin1, Cheng Zhong1, Feng Yang1
1School of Computer,Electronics and Information, Guangxi University, Nanning 530004, China

Abstract

A graphic sequence \( \pi = (d_1, d_2, \ldots, d_n) \) is said to be potentially \( K_{1^3,4} \)-graphic if there is a realization of \( \pi \) containing \( K_{1^3,4} \) as a subgraph, where \( K_{1^3,4} \) is the \( 1 \times 1 \times 1 \times 4 \) complete 4-partite graph. In this paper, we characterize the graphic sequences potentially \( K_{1^3,4} \)-graphic and the result is simple. In addition, we apply this characterization to compute the values of \( \sigma( K_{1^3,4}, n) \).

Keywords: Graph, Degree sequence, Potentially Ks 4-graphic .