{
  "id": "1704.06867",
  "version": "v1",
  "published": "2017-04-23T00:59:49.000Z",
  "updated": "2017-04-23T00:59:49.000Z",
  "title": "Relation between the skew-rank of an oriented graph and the independence number of its underlying graph",
  "authors": [
    "J. Huang",
    "S. C. Li",
    "H. Wang"
  ],
  "comment": "16 Page; 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "An oriented graph $G^\\sigma$ is a digraph without loops or multiple arcs whose underlying graph is $G$. Let $S\\left(G^\\sigma\\right)$ be the skew-adjacency matrix of $G^\\sigma$ and $\\alpha(G)$ be the independence number of $G$. The rank of $S(G^\\sigma)$ is called the skew-rank of $G^\\sigma$, denoted by $sr(G^\\sigma)$. Wong et al. [European J. Combin. 54 (2016) 76-86] studied the relationship between the skew-rank of an oriented graph and the rank of its underlying graph. In this paper, the correlation involving the skew-rank, the independence number, and some other parameters are considered. First we show that $sr(G^\\sigma)+2\\alpha(G)\\geqslant 2|V_G|-2d(G)$, where $|V_G|$ is the order of $G$ and $d(G)$ is the dimension of cycle space of $G$. We also obtain sharp lower bounds for $sr(G^\\sigma)+\\alpha(G),\\, sr(G^\\sigma)-\\alpha(G)$, $sr(G^\\sigma)/\\alpha(G)$ and characterize all corresponding extremal graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-04-23T00:59:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50"
    ],
    "keywords": [
      "independence number",
      "oriented graph",
      "sharp lower bounds",
      "multiple arcs",
      "cycle space"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}