Search

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]

In this article, we study problems where one has to prove that certain graph parameter attains its maximum at the star and its minimum at the path among the trees on a fixed number of vertices. We give many applications of the so-called generalized tree shift which seems to be a powerful tool to attack the problems of the above-mentioned kind. We show that the generalized tree shift increases the largest eigenvalue of the adjacency matrix and Laplacian matrix, decreases the coefficients of the characteristic polynomials of these matrices in absolute value. We will prove similar theorems for the independence polynomial and the edge cover polynomial. The generalized tree shift induces a partially ordered set on trees having fixed number of vertices. The smallest element of this poset is the path, largest element is the star. Hence, the above-mentioned results imply the extremality of the path and the star for these parameters. [ABSTRACT FROM AUTHOR]