On independent domination in direct products

Abstract

In \cite{nr-1996} Nowakowski and Rall listed a series of conjectures involving several different graph products. In particular, they conjectured that $i(G\times H)\ge i(G)i(H)$ where $i(G)$ is the independent domination number of $G$ and $G\times H$ is the direct product of graphs $G$ and $H$. We show this conjecture is false, and, in fact, construct pairs of graphs for which $\min \{i(G),i(H)\}-i(G\times H)$ is arbitrarily large. We also give the exact value of $i(G\times K_n)$ when $G$ is either a path or a cycle.

arXiv comment14 pages, 2 figures, 2 tables