Search

The multiplicity of the second‐largest eigenvalue of the adjacency matrix A(G) of a connected graph G, denoted by m(λ2,G), is the number of times of the second‐largest eigenvalue of A(G) appears. In 2019, Jiang, Tidor, Yao, Zhang, and Zhao gave an upper bound on m(λ2,G) for graphs G with bounded degrees, and applied it to solve a longstanding problem on equiangular lines. In this paper, we show that if G is a 3‐connected planar graph or 2‐connected outerplanar graph, then m(λ2,G)≤δ(G), where δ(G) is the minimum degree of G. We further prove that if G is a connected planar graph, then m(λ2,G)≤Δ(G); if G is a connected outerplanar graph, then m(λ2,G)≤max{2,Δ(G)−1}, where Δ(G) is the maximum degree of G. Moreover, these two upper bounds for connected planar graphs and outerplanar graphs, respectively, are best possible. [ABSTRACT FROM AUTHOR]

Given a digraph G, we propose a new method to find the recurrence equation for the number of vertices [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]

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]