کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6416157 | 1631102 | 2016 | 9 صفحه PDF | دانلود رایگان |
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, if the algebraic connectivity is greater than minâ¡{2kâ1â(δ+1)/mâ,2kâ12}, then G has at least k edge-disjoint spanning trees; for a multigraph G with multiplicity m and minimum degree δâ¥k, if the algebraic connectivity is greater than minâ¡{2(kâ1)â(δ+1)/mâ,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.
Journal: Linear Algebra and its Applications - Volume 493, 15 March 2016, Pages 82-90