{
  "id": "1702.02060",
  "version": "v1",
  "published": "2017-02-07T15:30:52.000Z",
  "updated": "2017-02-07T15:30:52.000Z",
  "title": "Maximizing the number of edges in optimal $k$-rankings",
  "authors": [
    "Rigoberto Florez",
    "Darren A. Narayan"
  ],
  "journal": "AKCE International Journal of Graphs and Combinatorics, 12.1 (2015) 1--8",
  "categories": [
    "math.CO"
  ],
  "abstract": "A $k$-ranking is a vertex $k$-coloring such that if two vertices have the same color any path connecting them contains a vertex of larger color. The rank number of a graph is smallest $k$ such that $G$ has a $k$-ranking. For certain graphs $G$ we consider the maximum number of edges that may be added to $G$ without changing the rank number. Here we investigate the problem for $G=P_{2^{k-1}}$, $C_{2^{k}}$, $K_{m_{1},m_{2},\\dots,m_{t}}$, and the union of two copies of $K_{n}$ joined by a single edge. In addition to determining the maximum number of edges that may be added to $G$ without changing the rank number we provide an explicit characterization of which edges change the rank number when added to $G$, and which edges do not.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-02-07T15:30:52.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "rank number",
      "maximum number",
      "edges change",
      "explicit characterization",
      "single edge"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}