On bounds for some graph invariantsReport as inadecuate

 On bounds for some graph invariants

On bounds for some graph invariants - Download this document for free, or read online. Document in PDF available to download.

Download or read this book online for free in PDF: 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/


Related documents