Fractional arboricity, strength and eigenvalues of graphs with fixed girth or clique number

التفاصيل البيبلوغرافية
العنوان: Fractional arboricity, strength and eigenvalues of graphs with fixed girth or clique number
المؤلفون: Ruifang Liu, Hong-Jian Lai, Zhen-Mu Hong, Zheng-Jiang Xia
المصدر: Linear Algebra and its Applications. 611:135-147
بيانات النشر: Elsevier BV, 2021.
سنة النشر: 2021
مصطلحات موضوعية: Numerical Analysis, Algebra and Number Theory, Spanning tree, Simple graph, Arboricity, 010102 general mathematics, 010103 numerical & computational mathematics, 01 natural sciences, Graph, Combinatorics, Moore bound, Discrete Mathematics and Combinatorics, Geometry and Topology, 0101 mathematics, Laplace operator, Clique number, Eigenvalues and eigenvectors, Mathematics
الوصف: Let c ( G ) , g ( G ) , ω ( G ) and μ n − 1 ( G ) denote the number of components, the girth, the clique number and the second smallest Laplacian eigenvalue of the graph G, respectively. The strength η ( G ) and the fractional arboricity γ ( G ) are defined by η ( G ) = min F ⊆ E ( G ) ⁡ | F | c ( G − F ) − c ( G ) and γ ( G ) = max H ⊆ G ⁡ | E ( H ) | | V ( H ) | − 1 , where the optima are taken over all edge subsets F and all subgraphs H whenever the denominator is non-zero, respectively. Nash-Williams and Tutte proved that G has k edge-disjoint spanning trees if and only if η ( G ) ≥ k ; and Nash-Williams showed that G can be covered by at most k forests if and only if γ ( G ) ≤ k . In this paper, for integers r ≥ 2 , s and t, and any simple graph G of order n with minimum degree δ ≥ 2 s t and either clique number ω ( G ) ≤ r or girth g ≥ 3 , we prove that if μ n − 1 ( G ) > 2 s − 1 t φ ( δ , r ) or μ n − 1 ( G ) > 2 s − 1 t N ( δ , g ) , then η ( G ) ≥ s t , where φ ( δ , r ) = max ⁡ { δ + 1 , ⌊ r δ r − 1 ⌋ } and N ( δ , g ) is the Moore bound on the smallest possible number of vertices such that there exists a δ-regular simple graph with girth g. As corollaries, sufficient conditions on μ n − 1 ( G ) such that G has k edge-disjoint spanning trees are obtained. Analogous result involving μ n − 1 ( G ) to characterize fractional arboricity of graphs with given clique number is also presented. Former results in Liu et al. (2014) [17] and Hong et al. (2016) [11] are extended, and the result in Liu et al. (2019) [18] is improved.
تدمد: 0024-3795
URL الوصول: https://explore.openaire.eu/search/publication?articleId=doi_________::08ed04e465d707d9e339498d2113f424
https://doi.org/10.1016/j.laa.2020.10.023
حقوق: CLOSED
رقم الأكسشن: edsair.doi...........08ed04e465d707d9e339498d2113f424
قاعدة البيانات: OpenAIRE