CYCLE DOMINATION POLYNOMIAL OF A GRAPH

Let $G(V, E)$ be a simple connected finite graph. Then a Hamilton path in a graph is a path that reaches every vertex, and a Hamilton cycle is a cycle that reaches every vertex. A graph with a Hamilton cycle is called Hamiltonian. A dominating set $S\subseteq V$ is said to be a cycle dominating set if the induced subgraph $\langle S \rangle$ is Hamiltonian. The min-cycle domination number of $G$, denoted by $\gamma_{\text {min}_{\circ}}(G)$, is the minimum cardinality of the cycle dominating sets in $G$ and the max-cycle domination number of $G$, denoted by $\gamma_{\text {max}_{\circ}}(G)$ is the maximum cardinality of the cycle dominating sets in $G$. Note that the min-cycle domination number of $G$ is at least 3 and the max-cycle domination number of $G$ is at most $|V(G)|$. Let $\mathcal D_\circ (G, i)$ be the family of cycle dominating sets of $G$ with cardinality $i$ and let $d_\circ(G, i) = |\mathcal D_\circ (G, i)|$. The polynomial $D_{\circ}(G, x) = \sum_{i = \gamma_{\min_{\circ}}(G)}^{\gamma_{\max_{\circ}}(G)}d_{\circ}(G, i) x^i$ is defined as the cycle domination polynomial of $G$. A root of $D_\circ(G, x)$ is called a cycle domination root of $G$. We obtain some basic properties of the cycle domination polynomial and compute this polynomial and its roots for some specific graphs. Received: November 18, 2025Revised: December 6, 2025Accepted: February 23, 2026