On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees

DOI10.1016/J.DISC.2022.113112MaRDI QIDQ2675869zbMATH OpenOpenAlexWikidataFDO

Authors Xiangxiang Liu, Ligong Wang, Hajo Broersma

Publication date 26 September 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

broomBrualdi-Solheid-Turán-type problemspectral radiusspider

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: We partly confirm a Brualdi-Solheid-Tur'{a}n type conjecture due to Nikiforov, which is a spectral radius analogue of the well-known ErdH{o}s-S'os Conjecture that any tree of order $t$ is contained in a graph of average degree greater than $t-2$. We confirm Nikiforov's Conjecture for all brooms and for a larger class of spiders. For our proofs we also obtain a new Tur'{a}n type result which might turn out to be of independent interest.

Recommendations

• Spectral radius conditions for the existence of all subtrees of diameter at most four
• A Spectral Erdős-Sós Theorem
• The Erdős-Sós conjecture for spiders of large size
• On a conjecture of spectral extremal problems
• The spectral radius of graphs without long cycles

Cites work

• A bound on the spectral radius of graphs with \(e\) edges
• A contribution to the Zarankiewicz problem
• A spectral condition for odd cycles in graphs
• Connected graphs without long paths
• Graphs with large maximum degree containing no odd cycles of a given length
• On maximal paths and circuits of graphs
• On the Turán number of forests
• Proof of a conjecture on the spectral radius of \(C_4\)-free graphs
• Some Inequalities for the Largest Eigenvalue of a Graph
• Spectral bounds for the clique and independence numbers of graphs
• Spectral extrema for graphs: the Zarankiewicz problem
• Spectral extrema of graphs: forbidden hexagon
• The Erdős-Sós conjecture for spiders
• The Erdős-Sós conjecture for spiders of four legs
• The Erdős-Sós conjecture for spiders of large size
• The spectral radius of graphs without long cycles
• The spectral radius of graphs without paths and cycles of specified length
• The spectral radius of graphs without trees of diameter at most four
• Turán numbers of multiple paths and equibipartite forests

Cited in

(8)

• Spectral radius conditions for the existence of all subtrees of diameter at most four
• The spectral radius of graphs without trees of diameter at most four
• On the \(\alpha\)-index of minimally 2-connected graphs with given order or size
• A Spectral Erdős-Sós Theorem
• Spectral radius of graphs of given size with forbidden subgraphs
• An \(A_{\alpha}\)-spectral Erdős-Sós theorem
• Spectral extremal results on trees
• A spectral Turán problem for a fixed tree

This page was built for publication: On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees

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