## 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