Spectral strengthening of a theorem on transversal critical graphs

Abstract: A transversal set of a graph

G

is a set of vertices incident to all edges of

G

. The transversal number of

G

, denoted by

a u (G)

, is the minimum cardinality of a transversal set of

G

. A simple graph

G

with no isolated vertex is called

a u

-critical if

a u (G - e) < a u (G)

for every edge

e i n E (G)

. For any

a u

-critical graph

G

with

a u (G) = t

, it has been shown that

| V (G) | l e 2 t

by ErdH{o}s and Gallai and that

| E (G) | l e t + 1 c h o o s e 2

by ErdH{o}s, Hajnal and Moon. Most recently, it was extended by Gy'arf'as and Lehel to

| V (G) | + | E (G) | l e t + 2 c h o o s e 2

. In this paper, we prove stronger results via spectrum. Let

G

be a

a u

-critical graph with

a u (G) = t

and

| V (G) | = n

, and let

l a m b d a_{1}

denote the largest eigenvalue of the adjacency matrix of

G

. We show that

n + l a m b d a_{1} l e 2 t + 1

with equality if and only if

G

is

t K_{2}

,

K_{s + 1} c u p (t - s) K_{2}

, or

C_{2 s - 1} c u p (t - s) K_{2}

, where

2 l e q s l e q t

; and in particular,

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

with equality if and only if

G

is

K_{t + 1}

. We then apply it to show that for any nonnegative integer

r

, we have

n l e f t (r + f r a c l a m b d a_{1} 2 i g h t) l e t + r + 1 c h o o s e 2

and characterize all extremal graphs. This implies a pure combinatorial result that

r | V (G) | + | E (G) | l e t + r + 1 c h o o s e 2

, which is stronger than ErdH{o}s-Hajnal-Moon Theorem and Gy'arf'as-Lehel Theorem. We also have some other generalizations.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Spectral strengthening of a theorem on transversal critical graphs