TY - JOUR

T1 - Spectral radius conditions for the existence of all subtrees of diameter at most four

AU - Liu, Xiangxiang

AU - Broersma, Hajo

AU - Wang, Ligong

N1 - Funding Information:
Supported by the National Natural Science Foundation of China (Nos. 12271439 and 11871398 ) and China Scholarship Council (No. 202006290071 ).
Publisher Copyright:
© 2023 The Authors

PY - 2023/4/15

Y1 - 2023/4/15

N2 - Let μ(G) denote the spectral radius of a graph G. We partly confirm a conjecture due to Nikiforov, which is a spectral radius analogue of the well-known Erdős-Sós Conjecture that any tree of order t is contained in a graph of average degree greater than t−2. Let Sn,k be the graph obtained by joining every vertex of a complete graph on k vertices to every vertex of an independent set of order n−k, and let Sn,k+ be the graph obtained from Sn,k by adding a single edge joining two vertices of the independent set of Sn,k. In 2010, Nikiforov conjectured that for a given integer k, every graph G of sufficiently large order n with μ(G)≥μ(Sn,k+) contains all trees of order 2k+3, unless G=Sn,k+. We confirm this conjecture for trees with diameter at most four, with one exception. In fact, we prove the following stronger result for k≥8. If a graph G with sufficiently large order n satisfies μ(G)≥μ(Sn,k) and G≠Sn,k, then G contains all trees of order 2k+3 with diameter at most four, except for the tree obtained from a star on k+2 vertices by subdividing each of its k+1 edges once.

AB - Let μ(G) denote the spectral radius of a graph G. We partly confirm a conjecture due to Nikiforov, which is a spectral radius analogue of the well-known Erdős-Sós Conjecture that any tree of order t is contained in a graph of average degree greater than t−2. Let Sn,k be the graph obtained by joining every vertex of a complete graph on k vertices to every vertex of an independent set of order n−k, and let Sn,k+ be the graph obtained from Sn,k by adding a single edge joining two vertices of the independent set of Sn,k. In 2010, Nikiforov conjectured that for a given integer k, every graph G of sufficiently large order n with μ(G)≥μ(Sn,k+) contains all trees of order 2k+3, unless G=Sn,k+. We confirm this conjecture for trees with diameter at most four, with one exception. In fact, we prove the following stronger result for k≥8. If a graph G with sufficiently large order n satisfies μ(G)≥μ(Sn,k) and G≠Sn,k, then G contains all trees of order 2k+3 with diameter at most four, except for the tree obtained from a star on k+2 vertices by subdividing each of its k+1 edges once.

KW - Brualdi-Solheid-Turán type problem

KW - Spectral radius

KW - Trees of diameter at most four

KW - UT-Hybrid-D

UR - http://www.scopus.com/inward/record.url?scp=85146434809&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2023.01.004

DO - 10.1016/j.laa.2023.01.004

M3 - Article

AN - SCOPUS:85146434809

SN - 0024-3795

VL - 663

SP - 80

EP - 101

JO - Linear algebra and its applications

JF - Linear algebra and its applications

ER -