DIMACS TR: 95-24

Clique-like Dominating Sets



Author: Stephen Penrice

ABSTRACT

Continuing work by B\'{a}cso and Tuza and Cozzens and Kelleher, we investigate dominating sets which induce subgraphs with small clique covering number, or small independence number. We show that if a graph $G$ is connected and contains no induced subgraph isomorphic to $P_6$ or $H_t$ (the graph obtained by subdividing each edge of $K_{1,t}, t \geq 3$), then $G$ has a dominating set which induces a connected graph with clique covering number at most $t-1$. We then show that if $G$ has no isolated vertices and contains no induced subgraph isomorphic to $mK_2$, then $G$ contains a dominating set with independence number at most $2m-2$. For both of these results, the bounds are best possible. Finally, we prove a theorem which implies similar bounds for a variety of classes of graphs, and we show that if $G$ is connected and contains no induced subgraph isomorphic to $P_k$ or $H_t$, then the domination number of $G$ is bounded above by a constant that depends only on $k$, $t$, and the clique number of $G$.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-24.ps.gz
DIMACS Home Page