Spectral extrema of graphs with fixed size: Cycles and complete bipartite graphs. (June 2021)

• Record Type: Journal Article
• Authors: Zhai, Mingqing; Lin, Huiqiu; Shu, Jinlong
• Is Part Of: European journal of combinatorics. Volume 95(2021)
• Publication Date: 2021-06
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103322
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: Nikiforov (2002) showed that if G is K r + 1 -free then the spectral radius ρ ( G ) ≤ 2 m ( 1 − 1 ∕ r ), which implies that G contains C 3 if ρ ( G ) > m . In this paper, we follow this direction in determining which subgraphs will be contained in G if ρ ( G ) > f ( m ), where f ( m ) ∼ m as m → ∞ . We first show that if ρ ( G ) ≥ m, then G contains K 2, r + 1 unless G is a star; and G contains either C 3 + or C 4 + unless G is a complete bipartite graph, where C t + denotes the graph obtained from C t and C 3 by identifying an edge. Secondly, we prove that if ρ ( G ) ≥ 1 2 + m − 3 4, then G contains pentagon and hexagon unless G is a book; and if ρ ( G ) > 1 2 ( k − 1 2 ) + m + 1 4 ( k − 1 2 ) 2, then G contains C t for every t ≤ 2 k + 2 . In the end, some related conjectures are provided for further research.