Mathematics – Combinatorics
Scientific paper
2005-10-18
Bolet\'in de la Sociedad Matematica Mexicana (3) Vol. 16 (2010) 73-94
Mathematics
Combinatorics
13 pages, 4 figures, We fix some mistakes and add some comments
Scientific paper
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)\leq \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 $$ \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: $$ |E(G)| \geq \alpha(G)-c(G)+ \Gamma(\alpha(G), \tau(G)). $$
Gitler Isidoro
Valencia Carlos E.
No associations
LandOfFree
Bounds for graph invariants does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Bounds for graph invariants, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds for graph invariants will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-194410