Edge Connectivity, Packing Spanning Trees, and Eigenvalues of Graphs

Abstract

Let $\mathcal{G}$ be the set of simple graphs (or multigraphs) $G$ such that for each $G\in \mathcal{G}$ there exists at least two non-empty disjoint proper subsets $V_1,V_2\subseteq V(G)$ satisfying $V(G)\setminus (V_1\cup V_2)\ne \varphi$ and edge connectivity ${\kappa }^{\prime }(G)=e(V_i,V(G)\backslash V_i)$ for $1\le i\le 2$. A multigraph is a graph with possible multiple edges, but no loops. Let $\tau (G)$ be the maximum number of edge-disjoint spanning trees of a graph $G$. Motivated by a question of Seymour on the relationship between eigenvalues of a graph $G$ and bounds of $\tau (G)$, we mainly give the relationship between the third largest (signless Laplacian) eigenvalue and the bound of ${\kappa }^{\prime }(G)$ and $\tau (G)$ of a simple graph or a multigraph $G\in \mathcal{G}$, respectively.

16 pages, 3 figures