Spectral radius of graphs of given size with forbidden subgraphs
Linear Algebra and its Applications · 2024-05 · 689 · 108-125
DOI: 10.1016/j.laa.2024.02.026 ↗Kurz gefasst
Fachartikel in der Zeitschrift Linear Algebra and its Applications, 2024-05. Verfasst von Yuxiang Liu und 1 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 26 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
Let $\rho(G)$ be the spectral radius of a graph $G$ with $m$ edges. Let $S_{m-k+1}^{k}$ be the graph obtained from $K_{1,m-k}$ by adding $k$ disjoint edges within its independent set. Nosal's theorem states that if $\rho(G)>\sqrt{m}$, then $G$ contains a triangle. Zhai and Shu showed that any non-bipartite graph $G$ with $m\geq26$ and $\rho(G)\geq\rho(S_{m}^{1})>\sqrt{m-1}$ contains a quadrilateral unless $G\cong S_{m}^{1}$ [M.Q. Zhai, J.L. Shu, Discrete Math. 345 (2022) 112630]. Wang proved that if $\rho(G)\geq\sqrt{m-1}$ for a graph $G$ with size $m\geq27$, then $G$ contains a quadrilateral unless $G$ is one of four exceptional graphs [Z.W. Wang, Discrete Math. 345 (2022) 112973]. In this paper, we show that any non-bipartite graph $G$ with size $m\geq51$ and $\rho(G)\geq\rho(S_{m-1}^{2})>\sqrt{m-2}$ contains a quadrilateral unless $G$ is one of three exceptional graphs. Moreover, we show that if $\rho(G)\geq\rho(S_{\frac{m+4}{2},2}^{-})$ for a graph $G$ with even size $m\geq74$, then $G$ contains a $C_{5}^{+}$ unless $G\cong S_{\frac{m+4}{2},2}^{-}$, where $C_{t}^{+}$ denotes the graph obtained from $C_{t}$ and $C_{3}$ by identifying an edge, $S_{n,k}$ denotes the graph obtained by joining each vertex of $K_{k}$ to $n-k$ isolated vertices and $S_{n,k}^{-}$ denotes the graph obtained by deleting an edge incident to a vertex of degree two, respectively.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Liu, Y., & Wang, L. (2024). Spectral radius of graphs of given size with forbidden subgraphs. Linear Algebra and its Applications, 689, 108-125. https://doi.org/10.1016/j.laa.2024.02.026
Vancouver
Liu Y, Wang L. Spectral radius of graphs of given size with forbidden subgraphs. Linear Algebra and its Applications. 2024;689:108-125. doi:10.1016/j.laa.2024.02.026
BibTeX
@article{Liu2024,
author = {Liu, Yuxiang and Wang, Ligong},
title = {Spectral radius of graphs of given size with forbidden subgraphs},
journal = {Linear Algebra and its Applications},
year = {2024},
volume = {689},
pages = {108--125},
doi = {10.1016/j.laa.2024.02.026}
}
EUVIMED