Maxima of the Q-index: Forbidden 4-cycle and 5-cycle

Abstract

This paper gives tight upper bounds on the largest eigenvalue q (G) of the signless Laplacian of graphs with no 4-cycle and no 5-cycle.

If n is odd, let F_n be the friendship graph of order n; if n is even, let F_n be F_n−1 with an extra edge hung to its center. It is shown that if G is a graph of order n ≥ 4, with no 4-cycle, then

q (G) < q (Fn) ,

unless G = Fn.

Let S_n,k be the join of a complete graph of order k and an independent set of order n − k. It is shown that if G is a graph of order n ≥ 6, with no 5-cycle, then

q (G) < q (S_n,2) ,

unless G = S_n,k.

It is shown that these results are significant in spectral extremal graph problems. Two conjectures are formulated for the maximum q (G) of graphs with forbidden cycles.