Article ID Journal Published Year Pages File Type
4949977 Discrete Applied Mathematics 2016 5 Pages PDF
Abstract
(2) Suppose that G is a graph with nonincreasing degree sequence d1,d2,…,dn and n≥⌊2st⌋+1. Let β=2st−1⌊2st⌋+1∑i=1⌊2st⌋+1di. Then γ(G)≤s/t, if β≥1, or if 0<β<1, n>⌊2s/t⌋+1+2s−2tβ and μn−1(G)>n(2s/t−2/t−β(⌊2s/t⌋+1))(⌊2s/t⌋+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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,