Spectral radius of graphs of given size with forbidden subgraphs

Yuxiang Liu, Ligong Wang

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

Let ρ(G) be the spectral radius of a graph G with m edges. Let Sm−k+1k be the graph obtained from K1,m−k by adding k disjoint edges within its independent set. Nosal's theorem states that if ρ(G)>m, then G contains a triangle. Zhai and Shu showed that any non-bipartite graph G with m≥26 and ρ(G)≥ρ(Sm1)>m−1 contains a quadrilateral unless G≅Sm1 M.Q. Zhai and J.L. Shu (2022) [25]. Wang proved that if ρ(G)≥m−1 for a graph G with size m≥27, then G contains a quadrilateral unless G is one out of four exceptional graphs Z.W. Wang (2022) [22]. In this paper, we show that any non-bipartite graph G with size m≥51 and ρ(G)≥ρ(Sm−12)>m−2 contains a quadrilateral unless G≅Sm1 or G≅Sm−12. Moreover, we show that if [Formula presented] for a graph G with even size m≥74, then G contains a C5+ unless [Formula presented], where Ct+ denotes the graph obtained from Ct and C3 by identifying an edge, Sn,k denotes the graph obtained by joining every vertex of Kk to n−k isolated vertices and Sn,k denotes the graph obtained from Sn,k by deleting an edge incident to a vertex of degree k, respectively.

Original languageEnglish
Pages (from-to)108-125
Number of pages18
JournalLinear Algebra and Its Applications
Volume689
DOIs
StatePublished - 15 May 2024

Keywords

  • Forbidden subgraph
  • Spectral radius
  • Spectral Turán type problem

Fingerprint

Dive into the research topics of 'Spectral radius of graphs of given size with forbidden subgraphs'. Together they form a unique fingerprint.

Cite this