Degree sequences and graphs with disjoint spanning trees

详细信息    查看全文

• 作者：Hong-Jian Lai^a ; ^b ; ^{hjlai@math.wvu.edu"" rel=""nofollow} ; Yanting Liang^b ; ^{lyt814@math.wvu.edu"" rel=""nofollow} ; Ping Li^b ; ^{liping@math.wvu.edu"" rel=""nofollow} ; Jinquan Xu^c
• 关键词：Graphic degree sequence ; ; none ; color ; black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-536PVVP-1&_mathId=mml15&_pii=S0166218X11001910&_issn=0166218X&_acct=C000050441&_version=1&_userid=1019048&md5=
• 刊名：Discrete Applied Mathematics
• 出版年：2011
• 出版时间：28 August 2011
• 年：2011
• 卷：159
• 期：14
• 页码：1447-1452
• 全文大小：232 K

文摘

The design of an n processor network with a given number of connections from each processor and with a desirable strength of the network can be modeled as a degree sequence realization problem with certain desirable graphical properties. A nonincreasing sequence d=(d₁,d₂,…,d_n) is graphic if there is a simple graph G with degree sequence d. In this paper, it is proved that for a positive integer k, a graphic sequence d has a simple realization G which has k edge-disjoint spanning trees if and only if either both n=1 and d₁=0, or n≥2 and both d_n≥k and .