• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Hong, Y. (Hong, Y..) [1] | Gu, X. (Gu, X..) [2] | Lai, H.-J. (Lai, H.-J..) [3] | Liu, Q. (Liu, Q..) [4]

Indexed by:

Scopus

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:

Algebraic connectivity; Arboricity; Eigenvalue; Fractional arboricity; Strength

Community:

  • [ 1 ] [Hong, Y.]College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian 350108, China
  • [ 2 ] [Gu, X.]Department of Mathematics, University of West Georgia, Carrollton, 30118, United States
  • [ 3 ] [Lai, H.-J.]Department of Mathematics, West Virginia University, Morgantown, 26506, United States
  • [ 4 ] [Liu, Q.]Center for Discrete Mathematics, Fuzhou University, Fuzhou, Fujian 350002, China

Reprint 's Address:

  • [Gu, X.]Department of Mathematics, University of West GeorgiaUnited States

Show more details

Related Keywords:

Related Article:

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:

Online/Total:93/10045612
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1