On bounds for some graph invariants

Abstract: Let

G

be a graph without isolated vertices and let

a l p h a (G)

be its stability number and

a u (G)

its covering number. The {it

a l p h a_{v}

-cover} number of a graph, denoted by

a l p h a_{v} (G)

, is the maximum natural number

m

such that every vertex of

G

belongs to a maximal independent set with at least

m

vertices. In the first part of this paper we prove that

a l p h a (G) l e q a u (G) [1 + a l p h a (G) - a l p h a_{v} (G)]

. We also discuss some conjectures analogous to this theorem. In the second part we give a lower bound for the number of edges of a graph

G

as a function of the stability number

a l p h a (G)

, the covering number

a u (G)

and the number of connected components

c (G)

of

G

. Namely, let

a l p h a

and

a u

be two natural numbers and let

Gamma(alpha, au)= min{sum_{i=1}^{alpha}�in{z_i}{2} | z_1+...+z_{alpha}= alpha+ au {and} z_i geq 0 forall i=1,..., alpha}.

Then if

G

is any graph, we have:

|E(G)| geq alpha(G)-c(G)+ Gamma(alpha(G), au(G)).

Recommendations

Cited in

(19)

This page was built for publication: On bounds for some graph invariants