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

author:

Hong, Yanmei (Hong, Yanmei.) [1] (Scholars:洪艳梅) | Gu, Xiaofeng (Gu, Xiaofeng.) [2] | Lai, Hong-Jian (Lai, Hong-Jian.) [3] | Liu, Qinghai (Liu, Qinghai.) [4] (Scholars:刘清海)

Indexed by:

EI Scopus SCIE

Abstract:

We investigate the relationship between the eigenvalues of a graph G and fractional spanning tree packing and coverings of G. Let omega(G) denote the number of components of a graph G. The strength eta(G) and the fractional arboricity gamma(G) are defined by eta(G) = min vertical bar X vertical bar/omega(G - X) - omega(G), and gamma(G) = max vertical bar E(H)vertical bar/vertical bar V(H)vertical bar - 1, 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 eta(G) >= k; and Nash-Williams proved that a graph G can be covered by at most k forests if and only if gamma(G) <= k. Let lambda(1)(G) (mu(i)(G), q(i)(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 delta >= 2s/t. Then eta(G) >= s/t if mu(n-1)(G) > 2s-1/t(delta+1), or if lambda(2) (G) < delta - 2s-1/t(delta+1), or if q(2) (G) < 2 delta - 2s-1/t(delta+1). (2) Suppose that G is a graph with nonincreasing degree sequence d(1), d(2), ... , d(n) and n >= left perpendicular 2s/t right perpendicular + 1. Let beta = 2s/t - 1/left perpendicular 2s/t right perpendicular + 1 Sigma(i=1) (left perpendicular 2s/t right perpendicular +1) d(i). Then gamma(G) <= s/t, if beta >= 1, or if 0 < beta < 1, n > left perpendicular 2s/t right perpendicular + 1 + 2s-2/t beta and mu(n-1)(G) > n(2s/t - 2/t - beta (left perpendicular 2s/t right perpendicular + 1))/(left perpendicular 2s/t right perpendicular + 1) (n - left perpendicular 2s/t right perpendicular - 1) Our result proves a stronger version of a conjecture by Cioaba and Wong on the relationship between eigenvalues and spanning tree packing, and sharpens former results in this area. (C) 2016 Elsevier B.V. All rights reserved.

Keyword:

Algebraic connectivity Arboricity Eigenvalue Fractional arboricity Strength

Community:

  • [ 1 ] [Hong, Yanmei]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350108, Fujian, Peoples R China
  • [ 2 ] [Gu, Xiaofeng]Univ West Georgia, Dept Math, Carrollton, GA 30118 USA
  • [ 3 ] [Lai, Hong-Jian]West Virginia Univ, Dept Math, Morgantown, WV 26506 USA
  • [ 4 ] [Liu, Qinghai]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350002, Fujian, Peoples R China

Reprint 's Address:

  • [Gu, Xiaofeng]Univ West Georgia, Dept Math, Carrollton, GA 30118 USA

Show more details

Related Keywords:

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 Discipline: ENGINEERING;

ESI HC Threshold:177

JCR Journal Grade:2

CAS Journal Grade:4

Cited Count:

WoS CC Cited Count: 8

SCOPUS Cited Count: 8

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Online/Total:314/10037504
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