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