Spectral conditions for edge connectivity and packing spanning trees in multigraphs

详细信息    查看全文

• 作者：Xiaofeng Gu ^{xgu@westga.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：05C50 ; 05C05 ; 05C40
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：15 March 2016
• 年：2016
• 卷：493
• 期：Complete
• 页码：82-90
• 全文大小：294 K

文摘

A multigraph is a graph with possible multiple edges, but no loops. The multiplicity of a multigraph is the maximum number of edges between any pair of vertices. We prove that, for a multigraph G with multiplicity m   and minimum degree δ≥2k$\delta \ge 2k$, if the algebraic connectivity is greater than $\min \{\frac{2k-1}{\lceil (\delta +1)/m\rceil },\frac{2k-1}{2}\}$, then G has at least k edge-disjoint spanning trees; for a multigraph G with multiplicity m   and minimum degree δ≥k$\delta \ge k$, if the algebraic connectivity is greater than $\min \{\frac{2(k-1)}{\lceil (\delta +1)/m\rceil },k-1\}$, then the edge connectivity is at least k. These extend some earlier results.

A balloon of a graph G is a maximal 2-edge-connected subgraph that is joined to the rest of G by exactly one cut-edge. We provide spectral conditions for the number of balloons in a multigraph, which also generalizes an earlier result.