Spectral radius of graphs of given size with forbidden subgraphs

No author found.

Abstract: Let

h o (G)

be the spectral radius of a graph

G

with

m

edges. Let

S_{m - k + 1}^{k}

be the graph obtained from

K_{1, m - k}

by adding

k

disjoint edges within its independent set. Nosal's theorem states that if

h o (G) > s q r t m

, then

G

contains a triangle. Zhai and Shu showed that any non-bipartite graph

G

with

m g e q 26

and

h o (G) g e q h o (S_{m}^{1}) > s q r t m - 1

contains a quadrilateral unless

G c o n g S_{m}^{1}

[M.Q. Zhai, J.L. Shu, Discrete Math. 345 (2022) 112630]. Wang proved that if

h o (G) g e q s q r t m - 1

for a graph

G

with size

m g e q 27

, then

G

contains a quadrilateral unless

G

is one of four exceptional graphs [Z.W. Wang, Discrete Math. 345 (2022) 112973]. In this paper, we show that any non-bipartite graph

G

with size

m g e q 51

and

h o (G) g e q h o (S_{m - 1}^{2}) > s q r t m - 2

contains a quadrilateral unless

G

is one of three exceptional graphs. Moreover, we show that if

h o (G) g e q h o (S_{f r a c m + 4 2, 2}^{-})

for a graph

G

with even size

m g e q 74

, then

G

contains a

C_{5}^{+}

unless

G c o n g S_{f r a c m + 4 2, 2}^{-}

, where

C_{t}^{+}

denotes the graph obtained from

C_{t}

and

C_{3}

by identifying an edge,

S_{n, k}

denotes the graph obtained by joining each vertex of

K_{k}

to

n - k

isolated vertices and

S_{n, k}^{-}

denotes the graph obtained by deleting an edge incident to a vertex of degree two, respectively.

Cites Work