The maximum spectral radius of {C3, C5}-free graphs of given size

摘要

In this paper we consider the extremal problem on adjacency spectral radius of {C-3, C-5}-free graphs. Assume that G is a graph with m edges having no isolated vertices, and let lambda be the spectral radius of its adjacency matrix. Firstly, by using the method of characterizing {C-3, C-5}-free non-bipartite graphs whose second largest eigenvalue is less than 4 root 5, we show that, if G is a {C-3, C-5}-free non-bipartite graph of size m, then @@@ [GRAPHICS] @@@ . @@@ Equality holds if and only if G congruent to C-7, where d(u) is the degree of vertex u and f denotes the number of 4-cycles in G. Secondly, we show that, if G is a {C-3, C-5}-free non-bipartite graph of odd size m, then lambda <= theta(m) with equality if and only if G congruent to RK2, m-3/2, where theta(m) is the largest root of @@@ chi(4) - chi(3) - (m - 3)chi(2) + (m - 4)chi + m - 5 = 0 @@@ and RK2, m-3/2 is obtained by replacing an edge of the complete bipartite graph K-2,K- m-3/2 with P5.

关键词