A sharp upper bound for the independence number

arXiv1007.5426MaRDI QIDQ6219962FDOQ6219962

Publication date: 30 July 2010

Abstract: An

r

-graph

G

is a pair

(V, E)

such that

V

is a set and

E

is a family of

r

-element subsets of

V

. The emph{independence number}

a l p h a (G)

of

G

is the size of a largest subset

I

of

V

such that no member of

E

is a subset of

I

. The emph{transversal number}

a u (G)

of

G

is the size of a smallest subset

T

of

V

that intersects each member of

E

.

G

is said to be emph{connected} if for every distinct

v

and

w

in

V

there exists a emph{path} from

v

to

w

(that is, a sequence

e_{1}, d o t s, e_{p}

of members of

E

such that

v i n e_{1}

,

w i n e_{p}

, and if

p g e q 2

, then for each

i i n 1, d o t s, p - 1

,

e_{i}

intersects

e_{i + 1}

). The emph{degree} of a member

v

of

V

is the number of members of

E

that contain

v

. The maximum of the degrees of the members of

V

is denoted by

D e l t a (G)

. We show that for any

1 l e q k < n

, if

G = (V, E)

is a connected

r

-graph,

| V | = n

, and

D e l t a (G) = k

, then [alpha(G) leq n - left lceil frac{n-1}{k(r-1)} ight ceil, quad au(G) geq left lceil frac{n-1}{k(r-1)} ight ceil,] and these bounds are sharp. The two bounds are equivalent.

This page was built for publication: A sharp upper bound for the independence number

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