Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs

M Zhai, H Lin, J Shu - European Journal of Combinatorics, 2021 - Elsevier
M Zhai, H Lin, J Shu
European Journal of Combinatorics, 2021Elsevier
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 …
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.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果