Indexed by:
Abstract:
We investigate the relationship between the eigenvalues of a graph G and fractional spanning tree packing and coverings of G. Let ω(G) denote the number of components of a graph G. The strength η(G) and the fractional arboricity γ(G) are defined by η(G)=min, where the optima are taken over all edge subsets X whenever the denominator is non-zero. The well known spanning tree packing theorem by Nash-Williams and Tutte indicates that a graph G has k edge-disjoint spanning tree if and only if η(G)≥k; and Nash-Williams proved that a graph G can be covered by at most k forests if and only if γ(G)≤k. Let λi(G) (μi(G), qi(G), respectively) denote the ith largest adjacency (Laplacian, signless Laplacian, respectively) eigenvalue of G. In this paper, we prove the following. (1) Let G be a graph with δ≥2s/t. Then η(G)≥s/t if μn−1(G)>, or if λ2(G)<δ−. (2) Suppose that G is a graph with nonincreasing degree sequence d1,d2,…,dn and n≥⌊⌋+1. Let β=⌋+1di. Then γ(G)≤s/t, if β≥1, or if 0<β<1, n>⌊2s/t⌋+1+. Our result proves a stronger version of a conjecture by Cioabă and Wong on the relationship between eigenvalues and spanning tree packing, and sharpens former results in this area. © 2016 Elsevier B.V.
Keyword:
Reprint 's Address:
Email:
Source :
Discrete Applied Mathematics
ISSN: 0166-218X
Year: 2016
Volume: 213
Page: 219-223
0 . 9 5 6
JCR@2016
1 . 0 0 0
JCR@2023
ESI HC Threshold:177
JCR Journal Grade:2
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count: 8
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: