Bounds for graph invariants
Isidoro Gitler, Carlos E. Valencia · arXiv (Cornell University) · 2005
Let G be a graph without isolated vertices and let α(G) be its stability number and τ(G) its covering number. The σv-cover number of a graph, denoted by σ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 α(G) ≤ τ(G)[1 + α(G) − σ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 α(G), the covering number τ(G) and the number of connected components c(G) of G. Namely, let a and t be two natural numbers and let a ∑ () zi Γ(a, t) = min | z1 + · · · + za = a + t and zi ≥ 0 ∀ i = 1,...,a. 2 i=1 Then if G is any graph, we have: 1