{
  "id": "1812.09396",
  "version": "v1",
  "published": "2018-12-21T22:30:57.000Z",
  "updated": "2018-12-21T22:30:57.000Z",
  "title": "Tuple domination on graphs with the consecutive-zeros property",
  "authors": [
    "María Patricia Dobson",
    "Valeria Leoni",
    "María Inés Lopez Pujato"
  ],
  "comment": "11 pages, 5 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "The $k$-tuple domination problem, for a fixed positive integer $k$, is to find a minimum sized vertex subset such that every vertex in the graph is dominated by at least $k$ vertices in this set. The $k$-tuple domination is NP-hard even for chordal graphs. For the class of circular-arc graphs, its complexity remains open for $k\\geq 2$. A $0,1$-matrix has the consecutive 0's property (C0P) for columns if there is a permutation of its rows that places the 0's consecutively in every column. Due to A. Tucker, graphs whose augmented adjancency matrix has the C0P for columns are circular-arc. In this work we study the $k$-tuple domination problem on graphs $G$ whose augmented adjacency matrix has the C0P for columns, for $ 2\\leq k\\leq |U|+3$, where $U$ is the set of universal vertices of $G$. From an algorithmic point of view, this takes linear time.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-12-21T22:30:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "consecutive-zeros property",
      "tuple domination problem",
      "complexity remains open",
      "minimum sized vertex subset",
      "augmented adjacency matrix"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}