# On bounds for some graph invariants

Let $G$ be a graph without isolated vertices and let $\alphaG$ be its stability number and $\tauG$ its covering number. The {\it $\alpha {v}$-cover} number of a graph, denoted by $\alpha {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 $\alphaG\leq \tauG1+\alphaG-\alpha {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 $\alphaG$, the covering number $\tauG$ and the number of connected components $cG$ of $G$. Namely, let $\alpha$ and $\tau$ be two natural numbers and let $$\Gamma\alpha,\tau= \min{\sum {i=1}^{\alpha}\bin{z i}{2} | z 1+ .+z {\alpha}= \alpha+\tau {and} z i \geq 0 \forall i=1, ., \alpha}.$$ Then if $G$ is any graph, we have: $$|EG| \geq \alphaG-cG+ \Gamma\alphaG, \tauG.$$

Author: Isidoro Gitler; Carlos E. Valencia

Source: https://archive.org/