Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs

NEW

Problem: For finite simple undirected graphs $G,H$ with $|V(G)|,|V(H)|\ge2$, characterize when the lexicographic product $G[H]$ is well-totally-dominated, i.e. has no isolated vertices and all inclusion-minimal total dominating sets have the same cardinality. This matches the cited paper’s definitions of nontrivial lexicographic product and well-total-domination.

Result: The characterization is as follows.

Let $\gamma_t(X)$ denote the total domination number. Then $G[H]$ is well-totally-dominated iff one of the following holds:

1. $H$ has an isolated vertex and $G$ is well-totally-dominated.

2. $H$ has no isolated vertices, $G$ is edgeless, and $H$ is well-totally-dominated.

3. $H$ has no isolated vertices, $G$ has at least one edge, $H$ is well-totally-dominated with $\gamma_t(H)=2$, and every nontrivial connected component of $G$ is complete.

In particular, if $G$ is connected and $|V(G)|\ge2$, then:

Proof sketch with the key structural lemma.

For $D\subseteq V(G[H])$, put $S=p_G(D)$ and $D_g=p_{H,g}(D)$. Let

Then $D$ is a minimal total dominating set of $G[H]$ iff:

• $S$ is a dominating set of $G$;
• for each $g\in I(S)$, $D_g$ is a minimal total dominating set of $H$;
• for each $g\in S\setminus I(S)$, $|D_g|=1$;
• every $g\in S\setminus I(S)$ either has an external $S$-private neighbor $v\notin S$ with $N_G(v)\cap S=\{g\}$, or is adjacent to an $S$-leaf.

This follows directly from the adjacency rule in $G[H]$: $(g,h)$ is totally dominated by $D$ iff either $g$ has a neighbor in $S$, or $h$ has a neighbor in $D_g$.

If $H$ has an isolated vertex, no fiber can locally total-dominate $H$, so $I(S)=\varnothing$. Thus minimal total dominating sets of $G[H]$ are exactly lifts of minimal total dominating sets of $G$, with one chosen vertex in each fiber. Hence $G[H]$ is WTD iff $G$ is WTD.

Assume now that $H$ has no isolated vertices and $G$ is connected of order at least $2$. Any maximal independent set $S$ of $G$, together with minimal total dominating sets in each fiber over $S$, gives a minimal total dominating set of $G[H]$. Hence $H$ must be WTD and $G$ must be well-covered. If the common size of minimal total dominating sets of $H$ is $t$, then these lifted sets have size $t\alpha(G)$.

Also, any minimal total dominating set of $G$ lifts with singleton fibers to a minimal total dominating set of $G[H]$, so every minimal total dominating set of $G$ must have size $t\alpha(G)$. Since $t\ge2$, this forces $\gamma_t(G)\ge2\alpha(G)$. But for connected noncomplete $G$, choosing two distance-two vertices in a maximal independent set gives a total dominating set of size at most $2\alpha(G)-1$, contradiction. Therefore $G$ is complete, so $\alpha(G)=1$ and $t=2$.

Conversely, if $G$ is complete and $H$ is WTD with $\gamma_t(H)=2$, the structural lemma shows every minimal total dominating set of $G[H]$ has size $2$: either one fiber contains a minimal total dominating set of $H$, or two fibers contain one vertex each. Hence $G[H]$ is WTD.

The disconnected case follows componentwise, since a disjoint union is WTD iff each component is WTD, and $G[H]$ decomposes over the components of $G$. This gives exactly the three cases above.

Citation: The problem is Problem 7.2 in Gözüpek, Hujdurović, and Milanič, “Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs,” Discrete Mathematics & Theoretical Computer Science 19(1), 2017. The resolution above is not cited there and is given here as a complete characterization.