Spectral radius and spanning trees of graphs

DOI10.1016/J.DISC.2023.113400MaRDI QIDQ6041529zbMATH OpenFDO

Authors Guoyan Ao, Rui-fang Liu, Jinjiang Yuan

Publication date 31 May 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2212.05455

zbMATH Keywords

closureleaf degreespanning treespectral radius

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: For integer $kgeq2,$ a spanning $k$-ended-tree is a spanning tree with at most $k$ leaves. Motivated by the closure theorem of Broersma and Tuinstra [Independence trees and Hamilton cycles, J. Graph Theory 29 (1998) 227--237], we provide tight spectral conditions to guarantee the existence of a spanning $k$-ended-tree in a connected graph of order $n$ with extremal graphs being characterized. Moreover, by adopting Kaneko's theorem [Spanning trees with constraints on the leaf degree, Discrete Appl. Math. 115 (2001) 73--76], we also present tight spectral conditions for the existence of a spanning tree with leaf degree at most $k$ in a connected graph of order $n$ with extremal graphs being determined, where $kgeq1$ is an integer.

Review text

A spanning \(k\)-ended-tree (\(k\geq 2\)) is a spanning tree with at most \(k\) pendant vertices. In the present paper, the authors provide tight (adjacency and signless Laplacian) spectral radius conditions for a connected graph of order \(n\) to have a spanning \(k\)-ended-tree, and characterize the extremal graphs. The leaf degree of a tree \(T\) is the maximum number of pendant vertices adjacent to \(v\) in \(T\) for any \(v \in V(T)\). The authors also give tight (adjacency and signless Laplacian) spectral radius conditions for the existence of a spanning tree with leaf degree at most \(k\) (\(k\geq 1\)) in a connected graph, and determine the extremal graphs. The proof of the two main theorems is based on ingenious applications of the degree sum condition of \textit{H. Broersma} and \textit{H. Tuinstra} [J. Graph Theory 29, No. 4, 227--237 (1998; Zbl 0919.05017)] and \textit{A. Kaneko}'s theorem [Discrete Appl. Math. 115, No. 1--3, 73--76 (2001; Zbl 0989.05023)], respectively.

Recommendations

• Spectral radius and edge‐disjoint spanning trees
• scientific article; zbMATH DE number 1484041
• On the spectral radius of graphs
• Spectral radius of graphs
• Spectral radius of graphs
• scientific article; zbMATH DE number 3972892
• On the spectral radius of trees
• Estimates of the spectral radius of graphs^*
• On the spectral radius of quasi-tree graphs
• The Laplacian spectral radius of trees and maximum vertex degree

Cites work

• A bound on the spectral radius of graphs
• A method in graph theory
• A note on Hamiltonian circuits
• Graph theory
• scientific article; zbMATH DE number 3760340 (Why is no real title available?)
• Independence trees and Hamilton cycles
• Maximizing the sum of the squares of the degrees of a graph
• Neighborhood unions and extremal spanning trees
• Note on Hamilton Circuits
• On a conjecture of Las Vergnas concerning certain spanning trees in graphs
• On three conjectures involving the signless Laplacian spectral radius of graphs
• Signless Laplacian spectral radius and Hamiltonicity
• Some sufficient spectral conditions on Hamilton-connected and traceable graphs
• Spanning 3-ended trees in \(k\)-connected \(K_{1,4}\)-free graphs
• Spanning k-ended trees in quasi-claw-free graphs
• Spanning trees with at most 3 leaves in \(K_{1,4}\)-free graphs
• Spanning trees with at most 4 leaves in \(K_{1, 5}\)-free graphs
• Spanning trees with at most \(k\) leaves in \(K_{1,4}\)-free graphs
• Spanning trees with constraints on the leaf degree
• Spanning trees with few leaves
• Spectral analogues of Erdős' and Moon-Moser's theorems on Hamilton cycles
• Spectral radius and Hamiltonian graphs
• Spectral radius and Hamiltonian properties of graphs
• Spectral radius and Hamiltonicity of graphs
• Spectral results on Hamiltonian problem
• Sufficient spectral conditions on Hamiltonian and traceable graphs

Cited in

(14)

• The maximum spectral radius of graphs without spanning linear forests
• Spanning \(k\)-ended trees of bipartite graphs
• The spanning k-trees, perfect matchings and spectral radius of graphs
• \(\mathcal{D}\)-index and \(\mathcal{Q}\)-index for spanning trees with leaf degree at most \(k\) in graphs
• Spanning k-trees and distance signless Laplacian spectral radius of graphs
• Characterizing spanning trees via the size or the spectral radius of graphs
• The \(A_{\alpha}\)-spectral radius and spanning trees of graphs
• Distance spectral conditions for \textit{ID}-factor-criticality and fractional \([a,b]\)-factor of graphs
• Tight conditions for spanning trees with leaf degree at most k in graphs
• Sufficient conditions for k-factors and spanning trees of graphs
• Spectral extremal problems on factors in tough graphs, and beyond
• Sufficient conditions for spanning trees with constrained leaf distance in a graph
• Sufficient conditions on the existence of factors in graphs involving minimum degree.
• Eigenvalues and factors: a survey

This page was built for publication: Spectral radius and spanning trees of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041529)