View PDF HTML (experimental)

Abstract:For a graph $G=(V,E),$ a set of vertices $D\subseteq V $ is called a dominating set if every vertex in $V\backslash D$ is adjacent to a vertex in $D.$ A domatic-$2$-partition of $G$ is a partition of its vertices into two disjoint dominating sets. In this paper, for a finite simple connected graph $G,$ we construct a graph dynamical system $F$ and show that the set of dominating sets of $G$ are in one-to-one correspondence with the image of the action map of $F$. Moreover, we obtain the set of all domatic-$2$-partitions of $G$ from the set of all periodic orbits of $F.$ Finally, we extended actions of two dynamical systems to an action of a free semigroup on two letters, and determine independent dominating sets and idomatic partitions using its maximal invariant subset with a reversible action.

Submission history

From: Mehmet Akif Erdal [view email]
[v1] Thu, 12 May 2022 20:10:23 UTC (11 KB)
[v2] Sun, 5 Jun 2022 20:51:27 UTC (12 KB)
[v3] Sun, 13 Sep 2026 18:53:21 UTC (11 KB)