关于蕴含K_(1~r,s)可图序列的一个充分条件
|
摘要
设K_(1~r,s)为k_1×k_2×…×k_(r+1)的完全(r+1)部图,其中k1=k2=…=kr=1,kr+1=s.将YIN提出的蕴含K12,s、K13,s可图序列的一个充分条件推广到一般情况,给出了s≥r≥2,n≥s+r条件下,n项可图序列π=(d1,d2,…,dn)蕴含K1r,s可图的一个充分条件.
K_(1~r,s) is defined as a k_1×k_2×…×k_(r+1) complete(r+1)-partite graph,where k1=k2 = … =kr=1 and kr+1 =s.The sufficient condition of potentially K12,s-graphic sequences and K13,s-graphic sequences,proposed by YIN,is generalized to K1 r,s-graphic sequences,and the sufficient condition on n-term graphic sequenceπ=(d1,d2,…,dn)that yields potentially K1 r,s-graphic sequence is obtained.
K_(1~r,s) is defined as a k_1×k_2×…×k_(r+1) complete(r+1)-partite graph,where k1=k2 = … =kr=1 and kr+1 =s.The sufficient condition of potentially K12,s-graphic sequences and K13,s-graphic sequences,proposed by YIN,is generalized to K1 r,s-graphic sequences,and the sufficient condition on n-term graphic sequenceπ=(d1,d2,…,dn)that yields potentially K1 r,s-graphic sequence is obtained.
引文
[1] YIN Jianhua.The characterization for a G-graphic sequence to have a realization containing K12,s[J].Graphs&Combinatorics,2012,28(4):1-11.
[2] YIN Jianhua.A condition that yields potentially K13,sgraphic sequences[J].Utilitas Mathematica,2015,97:119-128.
[3]赖春晖.蕴含Kp,1,1,...,1可图度序列[J].闽南师范大学学报:自然科学版,2004,17(4):11-13.
[4] YIN Jianhua.A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially Sr,s-graphic[J].Czechoslovak Mathematical Journal,2012,62(3):863-867.
[5] GOULD R J,JACOBSON M S,LEHEL J.Potentially G-graphic degree sequences[C]//ALAVYI,LICKZ,SCHWENK A J.Combinatorics,Graph Theory,and Algorithms.Kalamazoo:New Issues Press,1999:451-460.
[6] YIN Jianhua. A Rao-type characterization for a sequence to have a realization containing a split graph[J].Acta Mathematica Sinica,2011,311(21):2485-2489.
[7] LUO Rong,WARNER M.On potentially Kk-graphic sequence[J].Ars Combinatoria,2005,75(4):175-192.
[8] LUO Rong.On potentially Ck-graphic sequnces[J].Ars Combinatoria,2002,64:301-318.
[9] YIN Jianhua,LI Jiongsheng.Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size[J].Discrete Mathematics,2005,301(2/3):218-227.
[10]王礼萍.离散数学教程[M].北京:清华大学出版社,2014.
[2] YIN Jianhua.A condition that yields potentially K13,sgraphic sequences[J].Utilitas Mathematica,2015,97:119-128.
[3]赖春晖.蕴含Kp,1,1,...,1可图度序列[J].闽南师范大学学报:自然科学版,2004,17(4):11-13.
[4] YIN Jianhua.A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially Sr,s-graphic[J].Czechoslovak Mathematical Journal,2012,62(3):863-867.
[5] GOULD R J,JACOBSON M S,LEHEL J.Potentially G-graphic degree sequences[C]//ALAVYI,LICKZ,SCHWENK A J.Combinatorics,Graph Theory,and Algorithms.Kalamazoo:New Issues Press,1999:451-460.
[6] YIN Jianhua. A Rao-type characterization for a sequence to have a realization containing a split graph[J].Acta Mathematica Sinica,2011,311(21):2485-2489.
[7] LUO Rong,WARNER M.On potentially Kk-graphic sequence[J].Ars Combinatoria,2005,75(4):175-192.
[8] LUO Rong.On potentially Ck-graphic sequnces[J].Ars Combinatoria,2002,64:301-318.
[9] YIN Jianhua,LI Jiongsheng.Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size[J].Discrete Mathematics,2005,301(2/3):218-227.
[10]王礼萍.离散数学教程[M].北京:清华大学出版社,2014.