An \(A_{\alpha}\)-spectral Erdős-Sós theorem

Ming-Zhu Chen¹ ; Shuchao Li² ; Zhao-Ming Li³ ; Yuantian Yu² ; Xiao-Dong Zhang⁴

¹School of Science, Hainan University
²Faculty of Mathematics and Statistics, Central China Normal University
³Department of Mathematics, The University of Chicago
⁴School of Mathematical Sciences, MOE-LSC, SHL-MAC Shanghai Jiao Tong University

The electronic journal of combinatorics, Tome 30 (2023) no. 3

Résumé

Let $G$ be a graph and let $\alpha$ be a real number in $[0,1].$ In 2017, Nikiforov proposed the $A_\alpha$-matrix for $G$ as $A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G)$, where $A(G)$ and $D(G)$ are the adjacency matrix and the degree diagonal matrix of $G$, respectively. The largest eigenvalue of $A_{\alpha}(G)$ is called the $A_\alpha$-index of $G.$ The famous Erdős-Sós conjecture states that every $n$-vertex graph with more than $\frac{1}{2}(k-1)n$ edges must contain every tree on $k+1$ vertices. In this paper, we consider an $A_\alpha$-spectral version of this conjecture. For $n>k,$ let $S_{n,k}$ be the join of a clique on $k$ vertices with an independent set of $n-k$ vertices and denote by $S^+_{n,k}$ the graph obtained from $S_{n,k}$ by adding one edge. We show that for fixed $k\geq2,\,0<\alpha<1$ and $n\geq\frac{88k^2(k+1)^2}{\alpha^4(1-\alpha)}$, if a graph on $n$ vertices has $A_\alpha$-index at least as large as $S_{n,k}$ (resp. $S^+_{n,k}$), then it contains all trees on $2k+2$ (resp. $2k+3$) vertices, or it is isomorphic to $S_{n,k}$ (resp. $S^+_{n,k}$). These extend the results of Cioabă, Desai and Tait (2022), in which they confirmed the adjacency spectral version of the Erdős-Sós conjecture.

Détail

DOI : 10.37236/11593

Classification : 05C50, 15A18
Mots-clés : Erdős-Sós conjecture, Nikiforov's conjecture