On bounds for some graph invariants

Abstract

Let $G$ be a graph without isolated vertices and let $\alpha (G)$ be its stability number and $\tau (G)$ 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 $\alpha (G)\le \tau (G)[1+\alpha (G)-{\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 $\alpha (G)$, the covering number $\tau (G)$ and the number of connected components $c(G)$ of $G$. Namely, let $\alpha$ and $\tau$ be two natural numbers and let $$ Γ(α,τ)= \min{\sum_{i=1}^α\bin{z_i}{2} | z_1+...+z_α= α+τ{and} z_i \geq 0 \forall i=1,..., α}. $$ Then if $G$ is any graph, we have: $$|E(G)|\ge \alpha (G)-c(G)+\Gamma (\alpha (G),\tau (G)).$$

22 pages, 11 figures, Major changes

Cited by in corpus (2)

• Linear polynomial for the regularity of powers of edge ideals of very well-covered graphs
• Improving the Caro-Wei bound and applications to Turán stability