摘要
设G是简单图,其顶点集为V(G)={v_1,v_2,…,v_n},d_i为v_i的度,i=1,2,…,n.则π=(d_1,…,d_n)称为图G的度序列.设π=(d_1,…,d_n)是一非增的非负整数序列,若π是某个图G的度序列,则π称为可图的,G称为π的一个实现.对于给定的图H,称序列π=(d_1,…,d_n)是蕴含H可图的,如果π存在一个实现包含子图H.K_k,C_k,P_k分别表示k阶完全图,圈长为k的圈和路长为k的路.K_(Υ-1)—H(H是K_(Υ+1)的子图)表示从Υ+1阶完全图中删去H的边集.本文主要研究度序列中蕴含H可图序列的刻划问题,得到了以下结果:
1、完全解决了蕴含K_5—E_3可图序列的刻划问题,E_3表示5个顶点3条边的图.
2、刻划了蕴含K_5—C_4,K_5—P_4,K_5—Y_4和K_5—Z_4-可图序列,其中,Z_4表示K_4—P_2,Y_4表示5个顶点3个叶子的树.
3、刻划了蕴含R_3~6可图序列,R_k~n表示n个顶点的k正则图.
Given a simple graph G,let V(G)= {v_1,v_2,...,v_n} be the vertex set of G, and let d_i be the degree of v_i,i = 1,2,...,n.Thenπ=(d_1,...,d_n)is called the degree sequence of G.Letπ=(d_1,...,d_n)be a non-increasing nonnegative integer sequence,πis said to be graphic if it is the degree sequence of a simple graph G and G is called a realization ofπ.For given a graph H,a graphic sequenceπ=(d_1,d_2,...,d_n)is said to be potentially H-graphic if there exists a realization ofπcontaining H as a subgraph.Let K_k,C_k and P_k denote a complete graph on k vertices,a cycle on k vertices and a path on k + 1 vertices,respectively.K_(r+1)- H is the graph obtained from K_(r+1)by removing the edges set E(H)where H is a subgraph of K_(r+1).In this thesis,we focus on considering the characterizations on potentially H-graphic sequences in degree sequences,and get the following results:
1、The characterizations on the potentially K_5- E_3-graphic sequences is given, where E_3 denotes graphs on 5 vertices and 3 edges.
2、We characterize the potentially K_5 - C_4,K_5 - P_4,K_5 -Y_4 and K_5 - Z_4-graphic sequences where Z_4 is K_4 - P_2 and Y_4 is a tree on 5 vertices and 3 leaves.
3、We also characterize the potentially R_3~6-graphic sequences where R_k~n denotes a k-regular graph of order n.
引文
[1]Bondy J.A.,Murty U.S.R.,Graph Theory with Applications[M}.The Macmillan Press London.,1976
[2]陈纲,蕴含C_6的可图度序列[J].广西大学学报,28(2)2003,119-124
[3]陈纲,蕴含K_(1,1,2)可图序列的刻划[J].青岛科技大学学报,27(1)2006,86-88
[4]陈纲,蕴K(r,s,t)可图序列的一个极值问题[J].烟台大学学报,19(4)2006,245-252
[5]Chen Gang,A note on potentially K_(1,1,t)-graphic sequences[J].Australasian Journal of Combinatorics,37(2007),21-26
[6]陈纲,李西宁,蕴含K(1,t+e)的可图序列[J].漳州师范学院学报,20(3)2007,5-7
[7]陈纲,尹建华,范英梅,蕴含k~C_6的可图序列[J].广西师范大学学报,24(3)2006.26-29
[8]Erdos P.,Jacobson M.S.and Lehel J.,Graphs realizing the same degree sequences and their respective clique numbers[J].Graph Theory,Combinatorics and Application,Vol.1(Y.Alavi et al.,eds.),John Wiley and Sons,Inc.,New York,1991,439-449
[9]Eschen Elaine M.and Niu Jianbing,On potentially(K_4 - e)-graphic sequences[J].Australasian Journal of Combinatorics,29(2004),59-65
[10]Ferrara M.,Gould R.J.,and Schmitt J.,Potentially K~t_s-graphic degree sequences[J].submitted
[11]Ferrara M.,Gould R.J.,and Schmitt J.,Graphic Sequences with a Realization Con-taining a Friendship Graph[J].Ars Combinatoria,85(2007),161-171
[12]Gould R.J.,Jacobson M.S.and Lehel J.,Potentially G-graphic degree sequences[J].in Combinatorics,Graph Theory and Algorithms,Vol.2(Y.Alavi et al.,eds.),New Issues Press,Kalamazoo,MI,1999,451-460
[13]Hu Lili and Lai Chunhui,On potentially K_5 - C_4-graphic sequences[JI.accepted by Ars Combinatoria
[14]Hu Lili and Lai Chunhui,On potentially K_5 - E_3-graphic sequences[J],accepted by Ars Combinatoria
[15]Hu Lili and Lai Chunhui,On potentially 3-regular graph graphic sequences[J],ac-cepted by Utilitas Mathematica
[16]Hu Lili,Lai Chunhui and Wang Ping,On potentially K_5 - H-graphic sequences[J].accepted by Czechoslovak Mathematical Journal
[17]黄琴,蕴含K_m-e图的度序列[J].漳州师范学院学报,15(4)2002,26-28
[18l黄琴,蕴含K_5-e图的度序列[J].新疆大学学报,22(3)2005,276-284
[19]Kleitman D.J.and Wang D.L.,Algorithm for constructing graphs and digraphs with given valences and factors[J].Discrete Math.,6(1973),79-88
[20]赖春晖,蕴含C_k图的度序列[J].漳州师范学院学报,11(4)1997,27-31
[21]Lai Chunhui,A note on potentially K_4 - e graphical sequences[J].Australasian J.of Combinatorics 24(2001),123-127
[22]赖春晖.蕴含K_4-e可图序列的刻划[J].漳州师范学院学报。 15(3)2002,53-59
[23]Lai Chunhui,The Smallest Degree Sum that Yields Potentially C_k-graphical Se-quences [J].J.Combin.Math.Combin.Comput.49(2004),57-64
[24]Lai Chunhui,An extremal problem on potentially K_(p,1,1)-graphic sequences[J].Dis-crete Mathematics and Theoretical Computer Science7(2005),75-81
[25]Lai Chunhui,An extremal problem on potentially K_m- P_k-graphic sequences[J].accepted by International Journal of Pure and Applied Mathematics
[26]Lai Chunhui,An Extremal Problem On Potentially K_m- C_4-graphic Sequences[J].Journal of Combinatorial Mathematics and Combinatorial Computing,61(2007),59-63
[27]Lai Chunhui,The smallest degree sum that yields potentially K_(r+1)- Z-graphical Sequences[J].accepted by Ars Combinatoria
[28]Lai Chunhui and Hu Lili,An Extremal Problem On Potentially K_(r+1)- H-graphic Sequences[J].accepted by Ars Combinatoria
[29]Lai Chunhui and Hu Lili,A Survey on Potentially K_(r+1)- G-graphical Sequences,a lecture presented at GTCA,Beijing,2007
[30]Lai Chunhui and Sun Yuzhen,An Extremal Problem On Potentially K_(r+1)-(kP_2∪tK_2)-graphic Sequences[J].submitted
[31]Lal Chunhui,Yah Guiying,On potentially K_(r+1)- U-graphical Sequences[J].accepted by Utilitas Mathematica.
[32]李炯生,图的度序列[J].数学进展,23(3)1994,193-204
[33]Li Jiongsheng and Luo Rong,Potentially 3~C_1-Graphic Sequences[J].J.University of Science and Technology of China,29(1)(1999),1-8
[34]Li Jiongsheng,Luo Rong,Liu Yunkai,An Extremal Problem on Potentially 3~C_1-graphic Sequences[J].J.Math.Study,31(4)(1998),362-369
[35]Li Jiongsheng and Song Zixia,The smallest degree sum that yields potentially P_k-graphical sequences[J].J.Graph Theory,29(1998),63-72
[36]Li Jiongsheng and Song Zixia,On the potentially P_k-graphic sequences[J].Discrete Math.,195(1999),255-262
[37]Li Jiongsheng and Song Zixia,An extremal problem on the potentially P_k-graphic sequences[J].Discrete Math.,212(2000),223-231
[38]Li Jiongsheng,Song Zixia and Luo Rong,The Erdos-Jscobson-Lehel conjecture on po-tentially P_k-graphic sequence is true[J].Science in China(Series A),41(5)(1998),510-520
[39]Li Jiongsheng,Song Zixia and Wang Ping,An Erdos-Jacobson- Lehel conjec-ture about potentially P_k-graphic sequences[J].J.China University of Science and Technology,28(1)(1998),1- 9
[40]Li Jiongsheng and Yin Jianhua,A variation of an extremal theorem due to Woodall[J].Southeast Asian Bulletin of Math.,25(2001),427-434
[41]李炯生,尹建华,极值图论与度序列[J].数学进展,33(3)(2004),273-283
[42]Li Jiongsheng and Yin Jianhua,The Threshold for the Erdos,Jacobson and Lehel Conjecture to Be True[J].Acta Mathematica Sinica,English Series,22(4)2006,1133-1138
[43]Luo Rong,On potentially C_k-graphic Sequences[J].Ars Combinatoria,64(2002),301-318
[44]Luo Rong,Warner Morgan,On Potentially K_k-graphic Sequences[J].Ars Combin.75(2005),233-239
[45]Mantel W.,Problem 28,Wiskundige Opgaven[J].10(1907),60-61
[46]Rao S.B.,A Survey of theory of potentially P-graphic and forcibly P-graphic degree sequences[J],in Lecture Notes in Math,No.885,Springer Verlag,1981,417-440
[47]Turán P.,On an extremal problem in graph Theory[J].Mat.Lapok,48(1941),436-452
[48]尹建华.蕴含K_(1,1,3)的正可图序列的最小度和[J].海南大学学报,22(3)2004,200-204
[49]Yin Jianhua and Chen Gang,On Potentiall K_(r1,r2,…r_m)-graphic Sequences[J].Utilitas Mathematica,72(2007),149-161
[50]Yin Jianhua,Chen Gang and Chen Guoliang,On Potentially k~C_1-graphic Sequences[J].Journal of Combinatorial Mathematics and Combinatorial Computing,61(2007),141-148
[51]Yin Jianhua,Chen Gang and Schmitt J.R.,Graphic Sequences with a realization containing a generalized Friendship Graph[J].accepted by Discrete Math
[52]Yin Jianhua and Li Jiongsheng,The smallest degree sum that yields potentially K_(r,r)-graphic sequences[J].Sci.China Ser.A,45(6)(2002),694-705
[53]Yin Jianhua and Li Jiongsheng,An extremal problem on potentially K_(r,s)-graphic sequences[J].Discrete Math.,260(2003),295-305
[54]Yin Jiaahua and Li Jiongsheng,Two suffcient conditions for a graphic sequence to have a realization with prescribed clique size[J].Discrete Math.,301(2005),218-227
[55]Yin Jianhua and Li Jiongsheng,Potentially K_(r1,r2,…,r_l,l,s)a-graphic sequences[J].Dis-crete Mathematics,307(2007),1167-1177
[56]Yin Jianhua,Li Jiongsheng and Chen Guoliang,The smallest degree sum that yields potentially k~C_l-graphic sequences[J].Discrete Mathematics,270(2003),319-327
[57]Yin Jianhua,Li Jiongsheng and Chen Guoliang,A variation of a classical Turán-type extremal problem[J].European J.Combin.,25(2004),989-1002
[58]Yin Jianhua,Li Jiongsheng and Chen Guoliang,The Smallest Degree Sum that Yields Potentially K_(2,s)-graphic Sequences[J].Ars Combin.,74(2005),213-222
[59]Yin Jianhua,Li Jiongsheng and Mao Rui,An Extremal Problem on the Potentially K_(r+1)- e-Graphic Sequences[J].Ars Combinatoria 74(2005),151-159
[60]Yin Mengxiao,The Smallest Degree Sum That Yields Potentially K_(r+1)-K_3-Graphic Sequences[J].Acta Math.Appl.Sin.Engl.Ser.22(2006),no.3,451-456
[61]Yin Mengxiao and Yin Jianhua,On potentially H-graphic sequences[J].Czechoslovak Mathematical Journal,57(2)(2007),705-724
