Edge Connectivity, Packing Spanning Trees, and eigenvalues of Graphs

Cunxiang Duan, Ligong Wang, Xiangxiang Liu

Published 2017-04-20Version 1

Let $\tau(G)$ be the maximum number of edge-disjoint spanning trees of a graph $G$. A multigraph is a graph with possible multiple edges, but no loops. The multiplicity is the maximum number of edges between any pair of vertices. Motivated by a question of Seymour on the relationship between eigenvalues of a graph $G$ and bounds of $\tau(G)$, we use adjacency quotient matrix and signless Laplacian quotient matrix to get the relationship between eigenvalues of a simple graph $G$ and bounds of $\tau(G)$ and edge connectivity $\kappa'(G)$. And we study the relationship between eigenvalues and bounds of $\tau(G)$ and edge connectivity $\kappa'(G)$ in a multigraph $G$.