{
  "id": "math/0510387",
  "version": "v3",
  "published": "2005-10-18T17:44:23.000Z",
  "updated": "2013-08-30T15:15:54.000Z",
  "title": "On bounds for some graph invariants",
  "authors": [
    "Isidoro Gitler",
    "Carlos E. Valencia"
  ],
  "comment": "22 pages, 11 figures, Major changes",
  "journal": "Boletin de la Sociedad Matematica Mexicana (3) Vol. 16 (2010) 73-94",
  "categories": [
    "math.CO"
  ],
  "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)\\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)). $$",
  "revisions": [
    {
      "version": "v3",
      "updated": "2013-08-30T15:15:54.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69"
    ],
    "keywords": [
      "graph invariants",
      "stability number",
      "maximal independent set",
      "covering number",
      "maximum natural number"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math.....10387G"
    }
  }
}