Eigenvalues and triangles in graphs

Abstract: Bollob'as and Nikiforov [J. Combin. Theory, Ser. B. 97 (2007) 859--865] conjectured the following. If

G

is a

K_{r + 1}

-free graph on at least

r + 1

vertices and

m

edges, then

l a m b d a_{1}^{2} (G) + l a m b d a_{2}^{2} (G) l e q f r a c r - 1 r c d o t 2 m

, where

l a m b d a_{1} (G)

and

l a m b d a_{2} (G)

are the largest and the second largest eigenvalues of the adjacency matrix

A (G)

, respectively. In this paper, we confirm the conjecture in the case

r = 2

, by using tools from doubly stochastic matrix theory, and also characterize all families of extremal graphs. Motivated by classic theorems due to ErdH{o}s and Nosal respectively, we prove that every non-bipartite graph

G

of order

n

and size

m

contains a triangle, if one of the following is true: (1)

l a m b d a_{1} (G) g e q s q r t m - 1

and

G e q C_{5} c u p (n - 5) K_{1}

; and (2)

l a m b d a_{1} (G) g e q l a m b d a_{1} (S (K_{l f l o o r f r a c n - 1 2 f l o o r, l c e i l f r a c n - 1 2 c e i l}))

and

G e q S (K_{l f l o o r f r a c n - 1 2 f l o o r, l c e i l f r a c n - 1 2 c e i l})

, where

S (K_{l f l o o r f r a c n - 1 2 f l o o r, l c e i l f r a c n - 1 2 c e i l})

is obtained from

K_{l f l o o r f r a c n - 1 2 f l o o r, l c e i l f r a c n - 1 2 c e i l}

by subdividing an edge. Both conditions are best possible. We conclude this paper with some open problems.

Recommendations

Cites work

Cited in

(63)

This page was built for publication: Eigenvalues and triangles in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993261)