Acyclic dominating partitions
Louigi Addario‐Berry, Ross J. Kang, Tobias Müller · Journal of Graph Theory · 2009
Abstract Given a graph G=(V, E), let \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{P}}$\end{document} be a partition of V. We say that \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{P}}$\end{document} is dominating if, for each part P of \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{P}}$\end{document} , the set V\P is a dominating set in G (equivalently, if every vertex has a neighbor of a different part from its own). We say that \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{P}}$\end{document} is acyclic if for any parts P, P′ of \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{P}}$\end{document} , the bipartite subgraph G[P, P′] consisting of the edges between P and P′ in \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{P}}$\end{document} contains no cycles. The acyclic dominating number ad(G) of G is the least number of parts in any partition of V that is both acyclic and dominating; and we shall denote by ad(d) the maximum over all graphs G of maximum degree at most d of ad(G). In this article, we prove that ad(3)=2, which establishes a conjecture of P. Boiron, É. Sopena, and L. Vignal, DIMACS/DIMATIA Conference “Contemporary Trends in Discrete Mathematics”, 1997, pp. 1–10. For general d, we prove the upper bound ad(d)=O(dlnd) and a lower bound of ad(d)=Ω(d). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 292–311, 2010