2018/08/18 by Ruifang Liu, Hong‐Jian Lai, Liu, Ruifang +3
Computer Science · Materials Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Graphene research and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1808.06101
openalex publication_date 2018/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let τ(G) and κ'(G) denote the edge-connectivity and the spanning tree packing number of a graph G, respectively. Proving a conjecture initiated by Cioaba and Wong, Liu et al. in 2014 showed that for any simple graph G with minimum degree δ≥ 2k ≥ 4, if the second largest adjacency eigenvalue of G satisfies λ2(G) < δ- (2k-1)/(δ+1), then τ(G) ≥ k. Similar results involving the Laplacian eigenvalues and the signless Laplacian eigenvalues of G are also obtained. In this paper, we find a function f(δ, k, g) such that for every graph G with minimum degree δ≥ 2k ≥ 4 and girth g ≥ 3, if its second largest adjacency eigenvalue satisfies λ2(G) < f(δ, k, g), then τ(G) ≥ k. As f(δ, k, 3) = δ- (2k-1)/(δ+1), this extends the above-mentioned result of Liu et al. Related results involving the girth of the graph, Laplacian eigenvalues and the signless Laplacian eigenvalues to describe τ(G) and κ'(G) are also obtained.