Fractional spanning tree packing, forest covering and eigenvalues

详细信息    查看全文

• 作者：Yanmei Hong^a ; Xiaofeng Gu^b ; ^{xgu@westga.edu" class="auth_mail" title="E-mail the corresponding author} ; Hong-Jian Lai^c ; Qinghai Liu^d
• 关键词：Eigenvalue ; Algebraic connectivity ; Strength ; Arboricity ; Fractional arboricity
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 November 2016
• 年：2016
• 卷：213
• 期：Complete
• 页码：219-223
• 全文大小：375 K

文摘

We investigate the relationship between the eigenvalues of a graph 18c268c532d5c" title="Click to view the MathML source">G$G$ and fractional spanning tree packing and coverings of 18c268c532d5c" title="Click to view the MathML source">G$G$. Let ω(G)$\omega \left(G\right)$ denote the number of components of a graph 18c268c532d5c" title="Click to view the MathML source">G$G$. The strength η(G)$\eta \left(G\right)$ and the fractional arboricity γ(G)$\gamma \left(G\right)$ are defined by where the optima are taken over all edge subsets X$X$ whenever the denominator is non-zero. The well known spanning tree packing theorem by Nash-Williams and Tutte indicates that a graph 18c268c532d5c" title="Click to view the MathML source">G$G$ has k$k$ edge-disjoint spanning tree if and only if η(G)≥k$\eta \left(G\right)\ge k$; and Nash-Williams proved that a graph 18c268c532d5c" title="Click to view the MathML source">G$G$ can be covered by at most k$k$ forests if and only if γ(G)≤k$\gamma \left(G\right)\le k$. Let λ_i(G)${\lambda }_i\left(G\right)$ (μ_i(G)${\mu }_i\left(G\right)$, q_i(G)$q_i\left(G\right)$, respectively) denote the i$i$th largest adjacency (Laplacian, signless Laplacian, respectively) eigenvalue of 18c268c532d5c" title="Click to view the MathML source">G$G$. In this paper, we prove the following.

(1) Let 18c268c532d5c" title="Click to view the MathML source">G$G$ be a graph with 18cb9fcd33a4dd2c891" title="Click to view the MathML source">δ≥2s/t$\delta \ge 2s/t$. Then η(G)≥s/t$\eta \left(G\right)\ge s/t$ if ${\mu }_{n-1}\left(G\right)>\frac{2s-1}{t(\delta +1)}$, or if ${\lambda }_2\left(G\right)<\delta -\frac{2s-1}{t(\delta +1)}$, or if $q_2\left(G\right)<2\delta -\frac{2s-1}{t(\delta +1)}$.

(2) Suppose that 18c268c532d5c" title="Click to view the MathML source">G$G$ is a graph with nonincreasing degree sequence d₁,d₂,…,d_n$d_1,d_2,\dots ,d_n$ and c20a">$n\ge \lfloor \frac{2s}{t}\rfloor +1$. Let $\beta =\frac{2s}{t}-\frac{1}{\lfloor \frac{2s}{t}\rfloor +1}{\sum }_{i=1}^{\lfloor \frac{2s}{t}\rfloor +1}{d}_i$. Then γ(G)≤s/t$\gamma \left(G\right)\le s/t$, if β≥1$\beta \ge 1$, or if 0<β<1$0<\beta <1$, $n>\lfloor 2s/t\rfloor +1+\frac{2s-2}{t\beta }$ and

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.