Tuple domination on graphs with the consecutive-zeros property

DOI10.1016/J.ENTCS.2019.08.036arXiv1812.09396WikidataQ113317396 ScholiaQ113317396MaRDI QIDQ6311531FDOQ6311531

Authors: M. P. Dobson, V. Leoni, Maria Inés Lopez Pujato 

Publication date: 21 December 2018

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 $kgeq2$. 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 $2leqkleq|U|+3$, where $U$ is the set of universal vertices of $G$. From an algorithmic point of view, this takes linear time.

Mathematics Subject Classification ID

Graph theory (05Cxx) Mathematical programming (90Cxx)

This page was built for publication: Tuple domination on graphs with the consecutive-zeros property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6311531)