Novel ways of enumerating restrained dominating sets of cycles

Sushmita Paul; Ratanjeet Pratap Chauhan; Srinibas Swain

paper

Novel ways of enumerating restrained dominating sets of cycles

arXiv:2111.11140

Abstract

Let $G = (V, E)$ be a graph. A set $S \subseteq V$ is a restrained dominating set (RDS) if every vertex not in $S$ is adjacent to a vertex in $S$ and to a vertex in $V - S$ . The restrained domination number of $G$ , denoted by $γ_{r} (G)$ , is the smallest cardinality of a restrained dominating set of $G$ . Finding the restrained domination number is NP-hard for bipartite and chordal graphs. Let $G_{n}^{i}$ be the family of restrained dominating sets of a graph $G$ of order $n$ with cardinality $i$ , and let $d_{r} (G_{n}, i) = ∣ G_{n}^{i} ∣$ . The restrained domination polynomial (RDP) of $G_{n}$ , $D_{r} (G_{n}, x)$ is defined as $D_{r} (G_{n}, x) = \sum_{i = γ_{r} (G_{n})}^{n} d_{r} (G_{n}, i) x^{i}$ . In this paper, we focus on the RDP of cycles and have, thus, introduced several novel ways to compute $d_{r} (C_{n}, i)$ , where $C_{n}$ is a cycle of order $n$ . In the first approach, we use a recursive formula for $d_{r} (C_{n}, i)$ ; while in the other approach, we construct a generating function to compute $d_{r} (C_{n}, i)$ .