CERTIFIED DOMINATING SETS AND CERTIFIED DOMINATION POLYNOMIAL OF COMPLETE BIPARTITE GRAPH $K_3,n$

Abstract

Let $G=(V, E)$ be a simple graph. Then a dominating set $D$ is a certified dominating set of $G$ if every vertex $v \in D$ has either zero or at least two neighbours in $V-D$. Let $K_{3, n}$ be the complete bipartite graph with $n+3$ vertices and let $D_{c e r}\left(K_{3, n}, i\right)$ denote the family of certified dominating sets of $K_{3, n}$ with cardinality $i$. Let $d_{\text {cer }}\left(K_{3, n}, i\right)=\left|D_{\text {cer }}\left(K_{3, n}, i\right)\right|$. Then in this paper, we obtain a exact formula for $d_{c e r}\left(K_{3, n}, i\right)$. Using this formula, we construct the certified domination polynomial

$$
D_{c e r}\left(K_{3, n}, x\right)=\sum_{i=2}^{n+3} d_{c e r}\left(K_{3, n}, i\right) x^i
$$

and obtain some properties of this polynomial.

Received: November 4, 2024
Revised: November 29, 2024
Accepted: December 17, 2024