Spectral conditions for edge connectivity and packing spanning trees in multigraphs

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 delta >= 2k, if the algebraic connectivity is greater than min{2k-1/[(delta+1)/m, 2k-1/2} then G has at least k edge-disjoint spanning trees; for a multigraph G with multiplicity m and minimum degree delta >= 2k, if the algebraic connectivity is greater than min{2(k-1)/[(delta+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. (C) 2015 Elsevier Inc. All rights reserved.