EUVIMEDEUVIMED entdecken
Crossref

Spectral radius of graphs of given size with forbidden subgraphs

Yuxiang Liu, Ligong Wang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →