蕴含K_5-P_2可图序列的刻划

On Potentially K_5-P_2 -Graphic Sequences

对于给定的图H,称π是蕴含H可图的,如果π有一个实现包含H作为子图.K k,C k,Pk分别表示k阶完全图,圈长为k的圈和路长为k的路.K 5-P2表示从5阶完全图中删去长为2的路.Luo Rong[14]考虑了蕴含C k可图序列的刻划问题,并刻划了当k=3,4,5时,蕴含C k的可图序列.此外,Luo等人[15]刻划了蕴含K 4的可图序列,Eschen和Niu[16]刻划了蕴含K 4-e的可图序列,Yin Jianhua等人[23]刻划了当r=2,s=3和r=2,s=4时,蕴含K r,s的可图序列,其中K r,s是r×s完全二部图.Hu Lili等人[3-5]刻划了蕴含K 5-C4,K 5-Z4,K 5-E3的可图序列,徐正华等人[18]刻划了蕴含K1,4+e的可图序列,王艳[17]刻划了蕴含K 1,4+P2的可图序列,刘明静[13]等人刻划了蕴含K 5-Z5的可图序列.本文刻划了当n≥5时,蕴含K 5-P2的可图序列.

For Given a graph H, a graphic sequence π = （d1,d2,...,dn） is said to be potentially H graphical if it has a realization containing H as a subgraph. Let Kk , Ck and Pk denote a complete graph on k vertices, a cycle on k vertices and a path on k ＋ 1 vertices, respectively. Let Ks - P2 be a graph obtained by delete a path on 3vertices to K5 which has 5 vertices and 5 edges. Luo Rongcharacterized the potentially Ck -graphic sequences for each k = 3,4,5. Recently, Luo and Warnert have characterized the potentially K4 -graphic sequences. Eschen and Niu characterized the potentially K4 -e- graphic sequences . Yin and Chen characterized the potentially Kr,s -graphic sequences for r = 2, s = 3 and r = 2,s = 4. Hu and Lai characterized the potentially K 5-C4 , K5-Z4 and K5 - E3 -graphic sequences, Xu and Hu characterized the potentially K1,4＋e-graphic sequences, Wang characterized the potentially K1,4＋P2 - graphic sequences, and Liu and Hu characterized the potentially K5 -Z5 -graphic sequences. In this paper, we characterize the potentially K5 - P2 -graphic sequences.