Search

The spanning tree packing number of a graph G $G$, denoted by τ(G) $\tau (G)$, is the maximum number of edge‐disjoint spanning trees contained in G $G$. The study of τ(G) $\tau (G)$ is one of the classic problems in graph theory. Cioabă and Wong initiated to investigate τ(G) $\tau (G)$ from spectral perspectives in 2012 and since then, τ(G) $\tau (G)$ has been well studied using the second‐largest eigenvalue of the adjacency matrix in the past decade. In this paper, we further extend the results in terms of the number of edges and the spectral radius, respectively; and prove tight sufficient conditions to guarantee τ(G)≥k $\tau (G)\ge k$ with extremal graphs characterized. Moreover, we confirm a conjecture of Ning, Lu, and Wang on characterizing graphs with the maximum spectral radius among all graphs with a given order as well as fixed minimum degree and fixed edge connectivity. Our results have important applications in rigidity and nowhere‐zero flows. We conclude with some open problems in the end. [ABSTRACT FROM AUTHOR]

We show that a k-edge-connected graph on n vertices has at least [ABSTRACT FROM AUTHOR]

Let λ2(G) and τ (G) denote the second largest eigenvalue and themaximum number of edge-disjoint spanning trees of a graph G, respectively. Motivated by a question of Seymour on the relationship between eigenvalues of a graph G and bounds of τ (G), Cioaba andWong conjectured that for any integers d, k ≥ 2 and a d-regular graph G, if λ2(G) < d - 2k-1/d+1, then τ (G) ≥ k. They proved the conjecture for k = 2, 3, and presented evidence for the cases when k ≥ 4. Thus the conjecture remains open for k ≥ 4. We propose a more general conjecture that for a graph G with minimum degree δ ≥ 2k ≥ 4, if λ2(G) < δ - 2k-1 δ+1, then τ (G) ≥ k. In this article, we prove that for a graph G with minimum degree δ, each of the following holds. (i) For k {2, 3}, if δ ≥ 2k and λ2(G) < δ - 2k-1/δ+1, then τ (G) ≥ k. (ii) For k ≥ 4, if δ ≥ 2k and λ2(G) < δ - 3k-1/δ+1, then τ (G) ≥ k. Our results sharpen theorems of Cioaba and Wong and give a partial solution to Cioaba and Wong's conjecture and Seymour's problem. We also prove that for a graph G with minimum degree δ ≥ k ≥ 2, if λ2(G) < δ - 2(k-1) δ+1, then the edge connectivity is at least k, which generalizes a former result of Cioab? a. As corollaries, we investigate the Laplacian and signless Laplacian eigenvalue conditions on τ (G) and edge connectivity. [ABSTRACT FROM AUTHOR]