Ratio Mathematica Volume 47, 2023

Superior domination polynomial of cycles

Tejaskumar R*
A Mohamed Ismayil†

Abstract

Superior domination polynomial SD(G, x) =
∑n

t=γsd(G)
|sd(G, t)|xt

is a polynomial in which the power of the variable denotes the car-
dinality of a superior dominating set and the total number of sets of
same cardinality forms the coefficient of the variable. In this paper we
find the SD(G, Sn) of stars and SD(G, Cn) of cycles and properties
of the coefficients are discussed. The SD(G, x) different standard
graphs are obtained and the roots of the polynomial are tabulated.
Keywords: Superior distance, superior domination, neighbourhood
vertex, superior domination polynomial.
2020 AMS subject classifications: 05C12, 05C69, 05C31.1

*Research scholar, PG & Research Department of Mathematics, Jamal Mohamed Col-
lege(Affiliated to Bharathidasan University), Trichy, India; Mail Id: tejaskumaarr@gmail.com.

†Associate professor, PG & Research Department of Mathematics, Jamal Mohamed Col-
lege(Affiliated to Bharathidasan University), Trichy, India; Mail Id: amismayil1973@yahoo.co.in.
1Received on September 15, 2022. Accepted on December 15, 2022. Published on March 1, 2023.
DOI: 10.23755/rm.v41i0.819. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper
is published under the CC-BY licence agreement.

151



Tejaskumar R and A Mohamed Ismayil

1 Introduction

The graph G = (V, E) is a finite, undirected, simple, ordred pair where V (G) is a
set of vertices and E(G) is the set of edges. In 2009 Saeid Alikhani and Yee-hock
Peng[1] conceptualized the concept of domination polynomial. Domination is a
vast arena in graph theory, Ore[8] coined the term domination in graphs. A vast
literature about domination can be found in domination in graphs[3].

There are different types of distances in graph theory one being superior dis-
tance, Kathiresan and Marimuthu[7] were the pioneers of superior distance in
graphs. The same authors[6] put forth the concept of superior domination in
2008. A Mohamed Ismayil and Tejaskumar R[4] introduced eccentric domina-
tion polynomial which was the hybrid idea of combining eccentric domination[5]
and domination polynomial.

In this paper, a distance based domination polynomial called superior domi-
nation polynomial is introduced by coalescence of superior domination and domi-
nation polynomial. Standard formulas to find the coeffcients or the superior dom-
inating sets of stars Sn and cycles Cn for any value of n. Theorems realted to
properties of these coefficients are stated and proved. Superior domination poly-
nomial SD(G, x) of different standard graphs are calculated, their roots are tabu-
lated. For all the undefined terminologies and basic concepts of graphs refer the
book Graph theory by Frank Harary[2].

2 Preliminaries

Definition 2.1. [1]. Let D(G, i) be the family of dominating sets of a graph G
with cardinality i and let d(G, i) = |D(G, i)|. Then the domination polynomial
D(G, x) of G is defined as D(G, x) =

∑|V (G)|
i=γ(G)

d(G, i)xi, where γ(G) is the
domination number of G.

Definition 2.2. [7]. Let Duv = N[u] ∪ N[v]. A Duv-walk is defined as a u − v
walk in G that contains every vertex of Duv. The superior distance dD(u, v) from
u to v is the length of a shortest Du,v walk.

Definition 2.3. [7]. The superior neighbour of a vertex u is given by dD(u) =
min{dD(u, v) : v ∈ V (G)−{u}}. A vertex v(̸= u) is called a superior neighbour
of u if dD(u, v) = dD(u).

Definition 2.4. [6]. A vertex u is said to be a superior dominate a vertex v if v is
a superior neighbour of u.

152



Superior domination polynomial

Definition 2.5. [6]. A set S of vertices of G is called a superior dominating set of
G if every vertex V (G)−S is superior dominated by some vertex in S. A superior
dominating set G of minimum cardinality is a minimum superior dominating set
and its cardinality is called superior domination number of G and denoted by
γsd(G).

Theorem 2.1. [6]. For a cycle Cn the superior domination number is given by

γsd(Cn) =




n
3
, if n ≡ 0(mod 3)

n+2
3
, if n ≡ 1(mod 3)

n+1
3
, if n ≡ 2(mod 3)

3 Superior Domination Polynomial of Graphs
In this section, we defined superior domination polynomial, properties and results
related to superior domination polynomial are observed, stated and proved.

Definition 3.1. Superior domination polynomial is given by
SD(G, x) =

∑n
t=γsd(G)

|sd(G, t)|xt where |sd(G, t)| is the number of distinct
superior dominating set with cardinality t and γsd(G) is the superior domination
number.

Example 3.1. .

v5

v6

v3 v4

v1 v2

Figure 1: Net graph

Vertex Minimum superior distance dD Superior neighbour
v1 3 v2, v6
v2 3 v1, v6
v3 4 v1
v4 4 v2
v5 4 v6
v6 3 v1, v2

153



Tejaskumar R and A Mohamed Ismayil

From figure-1 we get {v3, v4, v5} is a superior dominating set with cardinality
3, {v1, v3, v4, v5}, {v2, v3, v4, v5}, {v3, v4, v5, v6} are superior dominating sets of
cardinality 4, {v1, v2, v3, v4, v5}, {v1, v3, v4, v5, v6}, {v2, v3, v4, v5, v6} are supe-
rior dominating sets of cardinality 5 and {v1, v2, v3, v4, v5, v6} is superior domi-
nating set with cardinality 6. Therefore superior domination polynomial is given
by SD(G, x) = x6 + 3x5 + 3x4 + x3.

Theorem 3.1. For a complete graph Kn the superior domination polynomial is
given by SD(Kn, x) = (1 + x)n − 1.

Proof. The degree of every vertex v ∈ Kn is n − 1. For any two vertices
u and v the number of vertices on their Duv-walk is given by |V (Kn)|. Since
|N[u]| = n and |N[v]| = n both the vertices have common neighbours and both u
and v are incident to each other. Therefore a Du,v-walk between u and v contains
all vertices of Kn and all the vertices of Kn forms the superior neighbour of any
v ∈ V (Kn) other than itself. By the definition of superior distance, the distance
between any two vertices is n − 1. Now by the definition of superior domination,
for every vertex of V (Kn)−S is superior dominated by some vertex in S which is
a superior dominating set and every vertex of V (Kn)−S has a superior neighbour
in S. Therefore SD(Kn, x) = (1 + x)n − 1.

Theorem 3.2. If two graphs are isomorphic then SD(G1, x) = SD(G2, x).

Proof. Let G1 and G2 be any two isomorphic graphs. Then there exist a one-
one and onto function between the vertex sets such that f : V (G1) → V (G2)
such that Vm and Vn are superior neighbours in G1 if and only if f(Vm) and
f(Vn) are superior neighbour of some vertex in G2. Therefore |SD(G1, n)| =
|SD(G2, n)| ∀ n. Therefore SD(G1, x) = SD(G2, x).

Example 3.2. In the figure 2 and 3 both the tetrahedral graph and complete graph
K4 are isomorphic to each other.

v3 v4

v1

v2

Fig:2-Tetrahedral graph Tg

v3 v4

v1 v2

Fig:3-Complete graph K4

SD(Tg, x) = x
4 + 4x3 + 6x2 + 4x.

SD(K4, x) = x
4 + 4x3 + 6x2 + 4x.

Hence Tg ∼= K4 implies SD(Tg, x) = SD(K4, x).

154



Superior domination polynomial

Definition 3.2. Superior domination polynomial of a star graph Sn is given by
SD(Sn, x) =

∑n
t=γsd(Sn)

|sd(Sn, t)|xt where |sd(Sn, t)| is the number of distinct
superior dominating sets with cardinality t and γsd(Sn) is the superior domination
number of a star graph.

Theorem 3.3. For a star graph Sn of order n where n ≥ 3, the following are true.

1. |sd(Sn, t)| = |sd(Sn−1, t − 1)| + |sd(Sn−1, t)|, t ∈ Z+, t ≤ n.

2. SD(Sn, x) = xSD(Sn−1, x) + SD(Sn−1, x).

3. SD(Sn, x) = x(x + 1)n−1.

Proof.

1. Let V (Sn) = {v1, v2, . . . vn}. All the pendant vertices form the superior
neighbours of central vertex v1 since deg(v1) = ∆(Sn) = n − 1. Here
we have (n−1)Ct−1 superior dominating sets of cardinality t. Therefore
|sd(Sn, t)| =(n−1) Ct−1, |sd(Sn−1, t−1)| =(n−2) Ct−2 and |sd(Sn−1, t)| =(n−2)
Ct−1.
But (n−1)Ct−1 =(n−2) Ct−2 +(n−2) Ct−1.
Therefore |sd(Sn, t)| = |sd(Sn−1, t − 1)| + |sd(Sn−1, t)|.

2. By theorem-3.3-(1) we have
|sd(Sn, t)| = |sd(Sn−1, t − 1)| + |sd(Sn−1, t)|.
When t = 1, |sd(Sn, 1)| = |sd(Sn−1, 0)| + |sd(Sn−1, 1)|.

=⇒ x|sd(Sn, 1)| = x|sd(Sn−1, 0)| + x|sd(Sn−1, 1)|.
When t = 2, |sd(Sn, 2)| = |sd(Sn−1, 1)| + |sd(Sn−1, 2)|.

=⇒ x2|sd(Sn, 2)| = x2|sd(Sn−1, 1)| + x2|sd(Sn−1, 2)|.
When t = 3, |sd(Sn, 3)| = |sd(Sn−1, 2)| + |sd(Sn−1, 3)|.

=⇒ x3|sd(Sn, 3)| = x3|sd(Sn−1, 2)| + x3|sd(Sn−1, 3)|.
When t = 4, |sd(Sn, 4)| = |sd(Sn−1, 3)| + |sd(Sn−1, 4)|.

=⇒ x4|sd(Sn, 4)| = x4|sd(Sn−1, 3)| + x4|sd(Sn−1, 4)|.
...

When t = n − 1, |sd(Sn, n − 1)| = |sd(Sn−1, n − 2)| + |sd(Sn−1, n − 1)|.
=⇒ xn−1|sd(Sn, n−1)| = xn−1|sd(Sn−1, n−2)|+xn−1|sd(Sn−1, n−

1)|.
When t = n, |sd(Sn, n)| = |sd(Sn−1, n − 1)| + |sd(Sn−1, n)|.

=⇒ xn|sd(Sn, n)| = xn|sd(Sn−1, n − 1)| + xn|sd(Sn−1, n)|.
Hence x|sd(Sn, 1)| + x2|sd(Sn, 2)| + x3|sd(Sn, 3)| + x4|sd(Sn, 4)| + · · · +
xn−1|sd(Sn, n − 1)| + xn|sd(Sn, n)| = x|sd(Sn−1, 0)| + x|sd(Sn−1, 1)| +
x2|sd(Sn−1, 1)| + x2|sd(Sn−1, 2)| + x3|sd(Sn−1, 2)| + x3|sd(Sn−1, 3)| +
x4|sd(Sn−1, 3)|+x4|sd(Sn−1, 4)|+· · ·+xn−1|sd(Sn−1, n−2)|+xn−1|sd(Sn−1, n−

155



Tejaskumar R and A Mohamed Ismayil

1)| + xn|sd(Sn−1, n − 1)| + xn|sd(Sn−1, n)|.

= x|sd(Sn−1, 0)| + x2|sd(Sn−1, 1)| + x3|sd(Sn−1, 2)| + x4|sd(Sn−1, 3)| +
· · ·+xn−1|sd(Sn−1, n−2)|+xn|sd(Sn−1, n−1)|+x|sd(Sn−1, 1)|+x2|sd(Sn−1, 2)|+
x3|sd(Sn−1, 3)|+x4|sd(Sn−1, 4)|+· · ·+xn−1|sd(Sn−1, n−1)|+xn|sd(Sn−1, n)|.

= x[x|sd(Sn−1, 1)|+x2|sd(Sn−1, 2)|+x3|sd(Sn−1, 3)|+x4|sd(Sn−1, 4)|+
· · ·+xn−1|sd(Sn−1, n−1)|]+x|sd(Sn−1, 1)|+x2|sd(Sn−1, 2)|+x3|sd(Sn−1, 3)|+
x4|sd(Sn−1, 4)| + · · · + xn−1|sd(Sn−1, n − 1)| + xn|sd(Sn−1, n)|.
Since |sd(Sn−1, 0)| = |sd(Sn−1, n)| = 0.

= x
∑n−1

t=1 |sd(Sn−1, t)|x
t +

∑n−1
t=1 |sd(Sn−1, t)|x

t.
SD(Sn, x) = x SD(Sn−1, x) + SD(Sn−1, x).

3. We prove this by mathematical induction.
When n = 3,

SD(Sn, x) = x(x + 1)
n−1

= x(x + 1)3−1

= x(x + 1)2

The result is true for n = 3.
When n = 4,

SD(Sn, x) = x(x + 1)
3

The result is true for n = 4.
Assume the result is true for all natural numbers less than n.

SD(Sn−1, x) = x(x + 1)
(n−1)−1

= x(x + 1)n−2

Now we prove the result for n.

SD(Sn, x) = x SD(Sn−1, x) + SD(Sn−1, x) using theorem3.3-(2)
= x[x(x + 1)n−2] + x(x + 1)n−2

= x(x + 1)n−2[x + 1]

= x(x + 1)n−2+1

= x(x + 1)n−1

∴ The result is true for all n.

Table: |sd(Sn, t)| is the number of superior dominating sets of Sn with
cardinality t where 1 ≤ t ≤ 15.

156



Superior domination polynomial

n
t

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 0
2 2 1
3 1 2 1
4 1 3 3 1
5 1 4 6 4 1
6 1 5 10 10 5 1
7 1 6 15 20 15 6 1
8 1 7 21 35 35 21 7 1
9 1 8 28 56 70 56 28 8 1
10 1 9 36 84 126 126 84 36 9 1
11 1 10 45 120 210 252 210 120 45 10 1
12 1 11 55 165 330 462 462 330 165 55 11 1
13 1 12 66 220 495 792 924 792 495 220 66 12 1
14 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
15 1 14 91 364 1001 2002 3003 3423 3003 2002 1001 364 91 14 1

Theorem 3.4. The following properties for the co-efficients of SD(Sn, x) holds.

1. |sd(Sn, 1)| = 1 for all n > 2.

2. |sd(Sn, n)| = 1 for all n ≥ 2.

3. |sd(Sn, n − 1)| = n − 1 for all n > 2.

4. |sd(Sn, n − 2)| =
(n − 1)(n − 2)

2
for all n ≥ 3.

5. |sd(Sn, n − 3)| =
(n − 1)(n − 2)(n − 3)

6
for all n ≥ 4.

6. |sd(Sn, n − 4)| =
(n − 1)(n − 2)(n − 3)(n − 4)

24
for all n ≥ 5.

7. |sd(Sn, t)| = |sd(Sn, n − t + 1)| for all n ≥ 3.

8. If SDn =
∑n

t=1 |sd(Sn, t)| for all n ≥ 3 then SDn = 2(SDn−1) with initial
condition SD3 = 4.

9. SDn =Total number of superior dominating sets in Sn = 2n−1 for all n ≥
3.

Proof.

1. Let V (Sn) = {v1, v2, . . . vn}. In a star graph Sn all the vertices form a
superior neighbour of central vertex v1 except itself. Therefore the only set
with single cardinality D = {v1} forms the superior dominating set of every
star graph Sn where n > 2. Therefore |sd(Sn, 1)| = 1 for all n > 2.

157



Tejaskumar R and A Mohamed Ismayil

2. The whole set of vertices V (Sn) forms the superior dominating set |sd(Sn, n)| =
1 for all n ≥ 2.

3. By mathematical induction on n. The result is true for n = 3,
since |sd(S3, 3 − 1)| = |sd(S3, 2)| = 2.
Assume the result is true for all natural numbers less than n.
Now we prove it for n ie, |sd(Sn−1, n − 2)| = n − 2.
By theorem-3.3-(1) and 3.4-(2)

|sd(Sn, n − 1)| = |sd(Sn−1, n − 2)| + |sd(Sn−1, n − 1)|
= (n − 2) + 1
= n − 1

∴ The result is true for all n.

4. By mathematical induction on n.
For n = 3, |sd(S3, 1)| = 1.
For n = 4, |sd(S4, 2)| = 3.
Assume the result is true for all natural numbers less than n,
ie, for n = n − 1, |sd(Sn−1, n − 3)| =

(n−2)(n−3)
2

Now we prove it for n. By theorem-3.3-(1) and 3.4-(3),

|sd(Sn, n − 2)| = |sd(Sn−1, n − 3)| + |sd(Sn−1, n − 2)|

=
(n − 2)(n − 3)

2
+ (n − 2)

=
(n − 2)(n − 3) + 2(n − 2)

2

=
(n − 2)(n − 3 + 2)

2

=
(n − 2)(n − 1)

2

=
(n − 1)(n − 2)

2

∴ The result is true for all n.

5. By mathematical induction on n.
For n = 4, |sd(S4, 1)| = 1.
For n = 5, |sd(S5, 2)| = 4.
Assume the result is true for all natural numbers less than n.
For n = n − 1, |sd(Sn−1, n − 4)| =

(n−2)(n−3)(n−4)
6

158



Superior domination polynomial

Now we prove it for n. By theorem-3.3-(1) and 3.4-(4),

|sd(Sn, n − 3)| = |sd(Sn−1, n − 4)| + |sd(Sn−1, n − 3)|

=
(n − 2)(n − 3)(n − 4)

6
+

(n − 2)(n − 3)
2

=
(n − 2)(n − 3)(n − 4 + 3)

6

=
(n − 1)(n − 2)(n − 3)

6

∴ The result is true for all n.

6. By mathematical induction on n.
The result is true for n = 5 since |sd(S5, 1)| = 1
For n = 6, |sd(S6, 2)| = 5.
Assume the result is true for all natural numbers less than n.
For n = n − 1, |sd(Sn−1, n − 5)| =

(n−2)(n−3)(n−4)(n−5)
24

Now we prove it for n. By theorem-3.3-(1) and 3.4-(5),

|sd(Sn, n − 4)| = |sd(Sn−1, n − 5)| + |sd(Sn−1, n − 4)|

=
(n − 2)(n − 3)(n − 4)(n − 5)

24
+

(n − 2)(n − 3)(n − 4)
6

=
(n − 2)(n − 3)(n − 4)(n − 5 + 4)

24

=
(n − 1)(n − 2)(n − 3)(n − 4)

24

∴ The result is true for all n.

7. By mathematical induction on n.
The result is true for n = 3 since |sd(S3, 1)| = |sd(S3, 3 − 1 + 1)| =
|sd(S3, 3)| = 1.
For n = 4, t = 2, |sd(S4, 2)| = |sd(S4, 4 − 2 + 1)| = |sd(S4, 3)| = 3.
Assume the result is true for all natural numbers less than n.
For n = n − 1, |sd(Sn−1, t − 1)| = |sd(Sn−1, (n − t + 1))|
Now we prove it for n. By theorem-3.3 we have,

|sd(Sn, t)| = |sd(Sn−1, t − 1)| + |sd(Sn−1, t)|
= |sd(Sn−1, (n − 1 − (t − 1) + 1))| + |sd(Sn−1, (n − 1 − (t) + 1))|
= |sd(Sn−1, (n − 1 − t + 1 + 1))| + |sd(Sn−1, (n − 1 − t + 1))|
= |sd(Sn−1, (n − t + 1))| + |sd(Sn−1, (n − t))|
= |sd(Sn, (n − t + 1))|

∴ The result is true for all n.

159



Tejaskumar R and A Mohamed Ismayil

8. SDn =
∑n

i=1 |sd(Sn, t)|
By theorem-3.3 we have

SDn =
n∑

i=1

[|sd(Sn−1, t − 1)| + |sd(Sn−1, t)|]

=
n−1∑
i=1

|sd(Sn−1, t)| +
n−1∑
i=1

|sd(Sn−1, t)|

= SDn−1 + SDn−1

SDn = 2[SDn−1]

9. By mathematical induction on n.
When n = 3,
SD3 = 2

3−1 = 22 = 4.
SD4 = 2

4−1 = 23 = 8.
Assume the result is true for all natural numbers less than n. Now we prove
it for n. Therefore SDn−1 = 2n−1−1 = 2n−2

Now

SDn = 2[SDn−1] from theorem-3.4-(8)
= 2[2n−2]

= 2n−2+1

= 2n−1

∴ The result is true for all n.
Hence the theorem.

4 Superior domination polynomial of cycle
Let sd(Cn, m) be the superior dominating set of cycle Cn with cardinality m.

K.M. Kathiresan and G. Marimuttu[6] proved theorem-2.1, for our convenience
we reframe theorem-2.1 as γsd(Cn) = ⌈n3 ⌉ ∀ n. Hereafter we denote the vertex
set V (G) = {v1, v2, . . . vn} = [n].

Lemma 4.1. For a cycle Cn, sd(Cn, m) = ∅ if m > n or m < ⌈n3 ⌉

Proof. Let Cn be a cycle, a superior dominating set D has the minimum
cardinality among the minimum superior dominating set with cardinality ⌈n

3
⌉ by

theorem-2.1. Therefore there is no proper subset of D which forms a superior
dominating set. Hence

sd(Cn, m) = ∅ where m < ⌈
n

3
⌉ = |D| (1)

160



Superior domination polynomial

There can not exists a superior dominating set greater than the order of the graph.
Therefore

sd(Cn, m) = ∅ if m > n (2)
From equation-(1) and (2) we obtain the result.

Observation 4.1. If a cycle Cn contains a maximal simple path of length 3k − 1,
3k or 3k + 1 then every dominating set of Cn must contain at least k, k + 1 or
k + 1 vertices respectively.

Lemma 4.2. Let L be a subset of the vertex set, L ⊆ [n]. If L is in sd(Cn−4, m−1)
or sd(Cn−5, m−1) ∋ L∪{v} ∈ sd(Cn, m) for v ∈ [n] then L ∈ sd(Cn−3, m−1).

Proof. Let L ∈ sd(Cn−4, m − 1) and L ∪ {v} ∈ sd(Cn, m) for v ∈ [n] then
by lemma-4.3 we consider {1, n − 4}, {2, n − 4} and {1, n − 5} as a subset of
L. Then L ∈ sd(Cn−3, m − 1) suppose L ∈ sd(Cn−5, m − 1) and L ∪ {v} ∈
sd(Cn, m) for v ∈ [n]. Then by lemma-4.3 {1, n − 5} must be a subset of L.
Hence L ∈ sd(Cn−3, m − 1).

Lemma 4.3. .

1. If sd(Cn−1, m − 1) = sd(Cn−3, m − 1) = ∅ then sd(Cn−2, m − 1) = ∅.

2. If sd(Cn−1, m−1) ̸= ∅ and sd(Cn−3, m−1) ̸= ∅ then sd(Cn−2, m−1) ̸= ∅.

3. If sd(Cn−1, m − 1) = sd(Cn−2, m − 1) = sd(Cn−3, m − 1) = ∅ then
sd(Cn, m) = ∅.

Proof.

1. Since sd(Cn−1, m−1) = sd(Cn−3, m−1) = ∅, by lemma-4.1, m−1 > n−1
or m − 1 < ⌈n−3

3
⌉. In both cases we have sd(Cn−2, m − 1) = ∅.

2. Suppose that sd(Cn−2, m−1) = ∅ by lemma-4.1, m−1 > n−2 or m−1 <
⌈n−2

3
⌉. If m−1 > n−2 then m−1 > n−3. Hence sd(Cn−3, m−1) = ∅, a

contradiction. Hence m−1 < ⌈n−2
3
⌉. So m−1 < ⌈n−1

3
⌉, sd(Cn−1, m−1) =

∅, also a contradiction.

3. Suppose sd(Cn, m) ̸= ∅. Let L ∈ sd(Cn, m) such that at least one vertex
labelled as vn or vn−1 is in L. If vn ∈ L, then by observation-4.1 at least one
vertex labelled as vn−1, vn−2 or vn−3 is in L. If vn−1 ∈ L or vn−2 ∈ L, then
L−{vn} ∈ sd(Cn−1, m−1), a contradiction. If vn−3 ∈ L, then L−{vn} ∈
sd(Cn−2, m − 1) a contradiction. Now suppose that vn−1 ∈ L. Then by
observation-4.1 at least one vertex labelled vn−2, vn−3 or vn−4 is in L. If
vn−2 ∈ L or vn−3 ∈ L, then L−{vn−1} ∈ sd(Cn−2, m−1), a contradiction.
If vn−4 ∈ L then L−{vn−1} ∈ sd(Cn−3, m−1), a contradiction. Therefore
sd(Cn, m) = ∅.

161



Tejaskumar R and A Mohamed Ismayil

Lemma 4.4. Suppose that sd(Cn, m) ̸= ∅ then we have

1. sd(Cn−1, m − 1) = sd(Cn−2, m − 1) = ∅ and sd(Cn−3, m − 1) ̸= ∅ if and
only if n = 3k and m = k for some k ∈ N.

2. sd(Cn−2, m − 1) = sd(Cn−3, m − 1) = ∅ and sd(Cn−1, m − 1) ̸= ∅ if and
only if m = n.

3. sd(Cn−1, m − 1) = ∅, sd(Cn−2, m − 1) ̸= ∅ and sd(Cn−3, m − 1) ̸= ∅ if
and only if n = 3k + 2 and m = ⌈3k+2

3
⌉ for some k ∈ N.

4. sd(Cn−1, m − 1) ̸= ∅, sd(Cn−2, m − 1) ̸= ∅ and sd(Cn−3, m − 1) = ∅ if
and only if m = n − 1.

5. sd(Cn−1, m − 1) ̸= ∅, sd(Cn−2, m − 1) ̸= ∅ and sd(Cn−3, m − 1) ̸= ∅ if
and only if ⌈n−1

3
⌉ + 1 ≤ m ≤ n − 2.

Proof.

1. Since sd(Cn−1, m−1) = sd(Cn−2, m−1) = ∅. By lemma-4.1 m−1 > n−1
or m−1 < ⌈n−2

3
⌉. If m−1 > n−1 then m > n by lemma-4.1 sd(Cn, m) =

∅ a contradiction. Therefore m < ⌈n−2
3
⌉ + 1 since sd(Cn, m) ̸= ∅ together

we have ⌈n
3
⌉ ≤ m ≤ ⌈n−2

3
⌉ + 1. Hence n = 3k and m = k for k ∈ N.

Conversely suppose if n = 3k, m = k for k ∈ N then by lemma-4.1
sd(Cn−1, m − 1) = sd(Cn−2, m − 1) = ∅ and sd(Cn−3, m − 1) ̸= ∅.

2. Since sd(Cn−2, m−1) = sd(Cn−3, m−1) = ∅ by lemma-4.1 m−1 > n−2
or m − 1 < ⌈n−3

3
⌉. If m − 1 < ⌈n−3

3
⌉ then m − 1 < ⌈n−1

3
⌉. Hence

sd(Cn−1, m − 1) = ∅ a contradiction. So we have m > n − 1 also since
sd(Cn−1, m − 1) ̸= ∅ we have m − 1 ≤ n − 1. Hence m = n.
Conversely suppose if m = n then by lemma-4.1 we have sd(Cn−2, m −
1) = sd(Cn−3, m − 1) = ∅ and sd(Cn−1, m − 1) ̸= ∅.

3. Since sd(Cn−1, m−1) = ∅ by lemma-4.1 m−1 > n−1 or m−1 < ⌈n−13 ⌉.
If m−1 > n−1 then m−1 > n−2 and by lemma-4.1 sd(Cn−2, m−1) =
sd(Cn−3, m − 1) = ∅ a contradiction so we must have m < ⌈n−13 ⌉ + 1. But
also we have m−1 ≥ ⌈n−2

3
⌉ because sd(Cn−2, m−1) ̸= ∅. Hence we have

⌈n−2
3
⌉+1 ≤ m < ⌈n−1

3
⌉+1. Therefore n = 3k+2 and m = k+1 = ⌈3k+2

3
⌉

for some k ∈ N.
Conversely suppose if n = 3k + 2, m = ⌈3k+2

3
⌉ for some k ∈ N then by

lemma-4.1 sd(Cn−1, m−1) = sd(C3k+1, k) = ∅, sd(Cn−2, m−1) ̸= ∅ and
sd(Cn−3, m − 1) ̸= ∅.

162



Superior domination polynomial

4. Since sd(Cn−3, m − 1) = ∅ by lemma-4.1 we have m − 1 > n − 3 or
m − 1 < ⌈n−3

3
⌉ since sd(Cn−2, m − 1) ̸= ∅ by lemma-4.1 we have ⌈n−23 ⌉ +

1 ≤ m ≤ n − 1. Therefore m − 1 < ⌈n−3
3
⌉ is not possible. Hence we must

have m−1 > n−3. Then m = n−1 or n but m ̸= n as sd(Cn−2, m−1) ̸= ∅.
Therefore m = n − 1.
Conversely suppose if m = n − 1 then by lemma-4.1 sd(Cn−1, m − 1) ̸= ∅
sd(Cn−2, m − 1) ̸= ∅ and sd(Cn−3, m − 1) = ∅.

5. Since sd(Cn−1, m−1) ̸= ∅, sd(Cn−2, m−1) ̸= ∅ and sd(Cn−3, m−1) ̸= ∅
then by applying lemma-4.1 we have ⌈n−1

3
⌉ ≤ m − 1 ≤ n − 1, ⌈n−2

3
⌉ ≤

m − 1 ≤ n − 2 and ⌈n−3
3
⌉ ≤ m − 1 ≤ n − 3 so ⌈n−1

3
⌉ ≤ m − 1 ≤ n − 3

and hence ⌈n−1
3
⌉ + 1 ≤ m ≤ n − 2.

Conversely suppose if ⌈n−1
3
⌉ + 1 ≤ m ≤ n − 2 then by lemma-4.1 we have

the result.

Theorem 4.1. For every n ≥ 4 and m ≥ ⌈n
3
⌉,

1. If sd(Cn−1, m − 1) = sd(Cn−2, m − 1) = ∅ and sd(Cn−3, m − 1) ̸= ∅ then
sd(Cn, m) = sd(Cn,

n
3
) = {{1, 4, . . . n−2}, {2, 5, . . . n−1}, {3, 6, . . . n}}.

2. If sd(Cn−2, m − 1) = sd(Cn−3, m − 1) = ∅ and sd(Cn−1, m − 1) ̸= ∅ then
sd(Cn, m) = sd(Cn, n) = {[n]}.

3. If sd(Cn−1, m − 1) = ∅, sd(Cn−2, m − 1) ̸= ∅ and sd(Cn−3, m − 1) ̸= ∅
then
sd(Cn, m) = {{1, 4, . . . n − 4, n − 1}, {2, 5, . . . n − 3, n}, {3, 6, . . . n −
2, n}}

⋃
{S

⋃ 
{n − 2}, if 1 ∈ S
{n − 1}, if 1 /∈ S, 2 ∈ S | S ∈ sd(Cn−3, m − 1)
{n}, otherwise

where S ⊆ V (Cn).

4. If sd(Cn−3, m − 1) = ∅, sd(Cn−2, m − 1) ̸= ∅ and sd(Cn−1, m − 1) ̸= ∅
then sd(Cn, m) = {[n] − {P}|P ∈ [n]}

5. If sd(Cn−1, m − 1) ̸= ∅, sd(Cn−2, m − 1) ̸= ∅ and sd(Cn−3, m − 1) ̸= ∅
then
sd(Cn, m) = {{n}

⋃
S | S ∈ sd(Cn−1, m − 1)

⋃
{S1



{n}, if n − 2 or n − 3 ∈ S1 for S1 ∈ sd(Cn−2, m − 1) or sd(Cn−1, m − 1)

{n − 1}, if n − 2 /∈ S1, n − 3 /∈ S1 or S1 ∈ sd(Cn−1, m − 1) ∩ sd(Cn−2, m − 1)

} ⋃

163



Tejaskumar R and A Mohamed Ismayil

{S2



{n − 2}, if 1 ∈ S2 for S2 ∈ sd(Cn−3, m − 1) or S2 ∈ sd(Cn−3, m − 1) ∩ sd(Cn−2, m − 1)

{n − 1}, if n − 3 ∈ S2 or n − 4 ∈ S2 for S2 ∈ sd(Cn−3, m − 1) or sd(Cn−2, m − 1)

}
where S, S1 and S2 are subsets of V (Cn).

Proof.

1. sd(Cn−1, m − 1) = sd(Cn−2, m − 1) = ∅ by lemma-4.4-(1) n = 3k,
m = k for some k ∈ N. Hence sd(Cn, m) = sd(Cn, n3 ) = {{1, 4, 7, . . . n−
2}, {2, 5, 8, . . . n − 1}, {3, 6, 9, . . . n}}.

2. sd(Cn−2, m − 1) = sd(Cn−3, m − 1) = ∅ and sd(Cn−1, m − 1) ̸= ∅ by
lemma-4.4-(2) m = n. Therefore sd(Cn, m) = (Cn, n) = {[n]}.

3. sd(Cn−1, m − 1) = ∅, sd(Cn−2, m − 1) ̸= ∅ and sd(Cn−3, m − 1) ̸= ∅ by
lemma-4.4-(3) n = 3k + 2, m = k + 1 for some k ∈ N we denote the
families
{{1, 4, . . . 3k − 2, 3k + 1}, {2, 5, . . . 3k − 1, 3k + 2}, {3, 6, . . . 3k, 3k + 3}}
and

{S
⋃ 

{3k}, if 1 ∈ S
{3k + 1}, if 1 /∈ S, 2 ∈ S | S ∈ sd(C3k−1, k)
{3k + 2}, otherwise

by L1 and L2 respectively. We shall prove that sd(C3k+2,k+1) = L1 ∪ L2.
Since sd(Ck, 3k) = {{1, 4, 7, . . . 3k−2}, {2, 5, 8, . . . 3k−1}, {3, 6, 9, . . . 3k}}
then L1 ⊆ sd(C3k+2, k + 1). Also it is obvious that L2 ⊆ sd(C3k+2, k + 1).
Hence L1 ∪ L2 ⊆ sd(C3k+2, k + 1).
Now let L ∈ sd(C3k+2, k + 1) then by observation-4.1 at least one of the
vertices labelled 3k + 2, 3k + 1 or 3k is in L. Suppose that 3k + 2 ∈ L then
by observation-4.1 at least one of vertices say 1, 2, 3, 3k + 1, 3k or 3k − 1
are in L. If 3k + 1 and at least one of {1, 2, 3} and also 3k and at least
one of {1, 2} are in L. Then L − {3k + 2} ∈ sd(C3k+1, k) a contradiction.
If {3, 3k} or 2, 3k − 1 is a subset of L, then L = S ∪ {3k + 2} for some
S ∈ sd(C3k, k) therefore L ∈ L1 if {1, 3k − 1} is a subset of L then
L − {3k + 2} ∈ sd(C3k+1, k) a contradiction. If {3, 3k − 1} is a subset of
L and {3k, 3k + 1} is not a subset of L then L − {3k + 2} ∈ sd(C3k−1, k)
hence L ∈ L2. If 3k + 1 or 3k is in L we have the result.

4. By lemma-4.4-(4) m = n − 1 therefore sd(Cn, m) = sd(Cn, n − 1) =
{[n] − {x}|x ∈ [n]}.

5. sd(Cn−1, m − 1) ̸= ∅, sd(Cn−2, m − 1) ̸= ∅ and sd(Cn−3, m − 1) ̸= ∅.
First suppose that S ∈ sd(Cn−1, m − 1) then S ∪ {n} ∈ sd(Cn, m). So

164



Superior domination polynomial

L1 = {{n} ∪ S|S ∈ sd(Cn−1, m − 1)} ⊆ sd(Cn, m). Now suppose that
sd(Cn−2, m − 1) ̸= ∅. Let S1 ∈ sd(Cn−2, m − 1) we denote

{S1
⋃ {{n}, if n − 2 or n − 3 ∈ S1 for S1 ∈ sd(Cn−2, m − 1) or sd(Cn−1, m − 1)

{n − 1}, if n − 2 /∈ S1, n − 3 /∈ S1 or S1 ∈ sd(Cn−1, m − 1) ∩ sd(Cn−2, m − 1)
simply by L2 by observation-4.1 at least one vertices labeled n−3, n−2 or
1 is in S1 if n − 2 or n − 3 is in S1. Then S1 ∪ {n} ∈ sd(Cn, m) otherwise
S1 ∪ {n − 1} ∈ sd(Cn, m). Hence L2 ⊆ sd(Cn, m) there we shall consider
sd(Cn−3, m − 1) ̸= ∅. Let S2 ∈ sd(Cn−3, m − 1) we denote
{S2

⋃ {{n − 2}, if 1 ∈ S2 for S2 ∈ sd(Cn−3, m − 1) or S2 ∈ sd(Cn−3, m − 1) ∩ sd(Cn−2, m − 1)
{{n − 1}, if n − 3 ∈ S2 or n − 4 ∈ S2 for S2 ∈ sd(Cn−3, m − 1) or sd(Cn−2, m − 1)

Simply by L3. If n − 3 or n − 4 is in S then S ∪ {n − 1} ∈ sd(Cn, m),
otherwise S2 ∪ {n − 2} ∈ sd(Cn, m). Hence L3 ⊆ L. Therefore we proved
that L1 ∪ L2 ∪ L3 ⊆ sd(Cn, m).
Now suppose that L ∈ sd(Cn, m) so by observation-4.1 L contains at least
one of the vertices say n, n − 1 or n − 2. If n ∈ L so by observation-4.1 at
least one of the vertices labelled n − 1, n − 2 or n − 3 and 1, 2, or 3 in L. If
n − 2 ∈ L or n − 3 ∈ L then L = S ∪ {n} for some S ∈ sd(Cn−2, m − 1).
Hence L ∈ L2 otherwise L = S ∪ {n − 1} sor some S ∈ sd(Cn−2, m − 1).
Hence L ∈ L2. If n − 1 or n − 2 is in L, we have the result.

Theorem 4.2. If sd(Cn, m) is the family of superior dominating sets of Cn with
cardinality m then |sd(Cn, m)| = |sd(Cn−1, m − 1)| + |sd(Cn−2, m − 1)| +
|sd(Cn−3, m − 1)|

Proof. We consider the five cases in theorem-4.1 we write theorem-4.1 in the
following form.

1. If sd(Cn−1, m − 1) = sd(Cn−2, m − 1) = ∅ and sd(Cn−3, m − 1) ̸= ∅ then
sd(Cn, m) = {{n − 2}

⋃
S1, {n − 1}

⋃
S2, {n}

⋃
S3|1 ∈ S1, 2 ∈ S2, 3 ∈

S3, S1, S2, S3 ∈ sd(Cn−3, m − 1)}.

2. If sd(Cn−2, m − 1) = sd(Cn−3, m − 1) = ∅ and sd(Cn−1, m − 1) ̸= ∅ then
sd(Cn, m) = {{n}

⋃
S|S ∈ sd(Cn−1, m − 1)}.

3. If sd(Cn−1, m − 1) = ∅, sd(Cn−2, m − 1) ̸= ∅ and sd(Cn−3, m − 1) ̸= ∅
then
sd(Cn, m) = {{n}

⋃
S1, {n − 1}

⋃
S2 or S1, S2 ∈ sd(Cn−2, m − 1), 1 ∈ S2}

⋃
(S

⋃


{n − 2}, if 1 ∈ S
{n − 1}, if 1 ∈ S, 2 ∈ S

)
where S ∈ sd(Cn−3, m − 1)

{n}, otherwise

4. If sd(Cn−3, m − 1) = ∅ and sd(Cn−2, m − 1) ̸= ∅, sd(Cn−1, m − 1) ̸= ∅
then sd(Cn, m) = {{n}

⋃
S1, {n − 1}

⋃
S2 or S1 ∈ sd(Cn−1, m − 1), S2 ∈

sd(Cn−2, m − 1)}.

165



Tejaskumar R and A Mohamed Ismayil

5. If sd(Cn−1, m − 1) ̸= ∅, sd(Cn−2, m − 1) ̸= ∅ and sd(Cn−3, m − 1) ̸= ∅
then sd(Cn, m) = {{n}

⋃
S|S ∈ sd(Cn−1, m − 1)}

⋃
{S1

⋃ {{n}, if n − 2 or n − 3 ∈ S1 for S1 ∈ sd(Cn−2, m − 1) or sd(Cn−2,m−1)
{n − 1}, if n − 2 /∈ S1, n − 3 /∈ S1 or S1 ∈ sd(Cn−1, m − 1)

⋂
sd(Cn−2, m − 1)

} ⋃
{S2

⋃ {{n − 2}, if 1 ∈ S2 for S2 ∈ sd(Cn−3, m − 1) or S2 ∈ sd(Cn−3, m − 1) ⋂ sd(Cn−2, m − 1)
{n − 2}, if n − 3 ∈ S2 or n − 4 ∈ S2 for S2 ∈ sd(Cn−3, m − 1) or sd(Cn−2, m − 1)

}
where S1 ∈ sd(Cn−2, m−1) or sd(Cn−1, m−1) and S2 ∈ {sd(Cn−3, m−1)
or sd(Cn−2, m − 1)}

⋂
sd(Cn−1, m − 1). Hence we have |sd(Cn, m)| =

|sd(Cn−1, m − 1)| + |sd(Cn−2, m − 1)| + |sd(Cn−3, m − 1)|.

Definition 4.1. Let sd(Cn, m) be the family of superior dominating sets of a cycle
Cn with cardinality n. Then the superior domination polynomial SD(Cn, x) of
Cn is defined as SD(Cn, x) =

∑n
m=⌈ n

3
⌉ |sd(Cn, m)|x

m where sd(Cn, m) is the
number of distinct superior dominating sets of same cardinality.

Theorem 4.3. For every n ≥ 4 SD(Cn, x) = x[SD(Cn−1, x) + SD(Cn−2, x) +
SD(Cn−3, x)] with initial values SD(C1, x) = x, SD(C2, x) = x2+2x, SD(C3, x) =
x3 + 3x2 + x.

Table: The co-efficients of SD(Cn, x) for 1 ≤ n ≤ 16

n
t

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1 0
2 0 0
3 3 3 1
4 0 6 4 1
5 0 5 10 5 1
6 0 3 14 15 6 1
7 0 0 14 28 21 7 1
8 0 0 8 38 48 28 8 1
9 0 0 3 36 81 75 36 9 1

10 0 0 0 25 102 150 110 45 10 1
11 0 0 0 11 99 231 253 154 55 11 1
12 0 0 0 3 72 282 456 399 208 66 12 1
13 0 0 0 0 39 273 663 819 598 273 78 13 1
14 0 0 0 0 14 210 786 1372 1372 861 350 91 14 1
15 0 0 0 0 3 125 765 1905 2590 2178 1200 440 105 15 1
16 0 0 0 0 0 56 608 2214 4096 4560 3312 1628 544 120 16 1

Theorem 4.4. The following properties hold for co-efficients of SD(Cn, x).

1. |sd(C3n, n)| = 3, ∀ n ∈ N.

2. |sd(Cn, m)| = |sd(Cn−1, m−1)|+ |sd(Cn−2, m−1)|+ |sd(Cn−3, m−1)|,
∀ n ≥ 4, m ≥ ⌈n

3
⌉,

166



Superior domination polynomial

3. |sd(C3n+2, n + 1)| = 3n + 2, ∀ n ∈ N.

4. |sd(C3n+1, n + 1)| =
n(3n+7)+2

2
, ∀ n ∈ N.

5. |sd(Cn, m)| = 1, ∀ n ≥ 3.

6. |sd(Cn, n − 1)| = n, ∀ n ≥ 3.

7. |sd(Cn, n − 2)| =
(n−1)n

2
, ∀ n ≥ 3.

8. |sd(Cn, n − 3)| =
(n−4)(n)(n+1)

6
, ∀ n ≥ 4.

9.
∑3m

n=m |sd(Cn, m)| = 3
∑3m−3

n=m−1 |sd(Cn, m − 1)|, ∀ m ≥ 4.

10. 1 = |sd(Cn, n)| < |sd(Cn+1, n)| < |sd(Cn+2, n)| < · · · < |sd(C2n−1, n)| <
|sd(C2n, n)| > |sd(C2n+1, n)| > · · · > |sd(C3n−1, n)| > |sd(C3n, n)| = 3,
∀ n ≥ 3.

11. If An =
∑n

m=⌈ n
3
⌉ |sd(Cn, m)| then for every n ≥ 4, An = An−1 + An−2 +

An−3 with initial values A1 = 1, A2 = 3 and A3 = 7.

Proof.

1. Since |sd(Cn, 3n)| = {{1, 4, 7, . . . 3n−2}, {2, 5, 8, . . . 3n−1}, {3, 6, 9, . . . 3n}},
so |sd(C3n, n)| = 3.

2. It follows from theorem-4.2.

3. By induction on n, the result is true for n = 1, because
|sd(C2, 5)| = {{1, 3}, {1, 4}, {2, 4}, {2, 5}, {3, 5}}. Suppose result is true
for all n − 1 then we prove for n. By (1),(2) and induction we have

|sd(C3n+2, n + 1)| = |sd(C3n+1, n)| + |sd(C3n, n)| + |sd(C3n−1, n)|
= 3n + 2

4. By mathematical induction |sd(C2, 4)| = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}.
So |sd(C4, 2)| = 6, the result is true for n = 1. Now suppose that the result
is true for all natural numbers less than n and we prove it for n.
By (1),(2),(3) and induction we have

|sd(C3n+1, n + 1)| = |sd(C3n, n)| + |sd(C3n−1, n)| + |sd(C3n−2, n)|

= 3 + 3(n − 1) + 2 + (n − 1)
3(n − 1) + 7) + 2

2

=
n(3n + 7) + 2

10

167



Tejaskumar R and A Mohamed Ismayil

5. It is obvious that for a graph with n vertices |sd(G, n)| = 1.

6. It is obvious that for a graph G with n vertices |sd(G, n − 1)| = n.

7. By induction on n. The result is true for n = 3. Since |sd(C3, 1)| = 3.
Assume it is true for all n − 1. We prove for n. By parts (1), (2), (4), (5)
and induction

|sd(Cn, n − 2)| = |sd(Cn−1, n − 3)| + |sd(Cn−2, n − 3)| + |sd(Cn−3, n − 3)|

=
(n − 2)(n − 1)

2
+ n − 2 + 1

=
(n − 1)n

2

8. By induction on n. The result is true for n = 4. Since |sd(C4, 1)| = 0.
Assume the result is true for all n − 1. We prove for n, by parts (2), (6), (7)
and induction we have

|sd(Cn, n − 3)| = |sd(Cn−1, n − 4)| + |sd(Cn−2, n − 4)| + |sd(Cn−3, n − 4)|

=
(n − 5)(n − 1)n

6
+

(n − 2)(n − 3)
2

+ n − 3

=
(n − 4)n(n + 1)

6

9. Proof by induction on m. Suppose m = 3 then
∑9

n=3 sd(Cn, 3) = 54 =

3
∑6

n=2 |sd(Cn, 2)|. Now suppose the result is true for every m < t and we
prove for m = t
3t∑

n=t

|sd(Cn, t)| =
3t∑

n=t

|sd(Cn−1, t − 1)| +
3t∑

n=t

|sd(Cn−2, t − 1)| +
3t∑

n=t

|sd(Cn−3, t − 1)|

= 3

3(t−1)∑
n=t−1

|sd(Cn−1, t − 2)| + 3
3(t−1)∑
n=t−1

|sd(Cn−2, t − 2)| + 3
3(t−1)∑
n=t−1

|sd(Cn−3, t − 2)|

= 3

3t−3∑
n=t−1

|sd(Cn, t − 1)|

10. We plan for every m, |sd(Cn, m)| < |sd(Cn+1, m)| for m ≤ n ≤ 2m − 1
and |sd(Cn, m)| > |sd(Cn+1, m)| for 2m ≤ n ≤ 3m − 1. We prove first
inequality by induction on m. The result hold for m = 3. Suppose that
result is true for all m ≤ t. Now we prove it for m = t + 1. That is
|sd(Cn, t + 1)| < |sd(Cn+1, t + 1)| for t + 1 ≤ n ≤ 2t + 1.

|sd(Cn, t + 1)| = |sd(Cn−1, t)| + |sd(Cn−2, t)| + |sd(Cn−3, t)|
< |sd(Cn, t)| + |sd(Cn−1, t)| + |sd(Cn−2, t)|
= |sd(Cn+1, t + 1)|

The other inequality follows in same way.

168



Superior domination polynomial

11. By theorem-4.2, we have

An =

n∑
m=⌈ n

3
⌉

|sd(Cn, m)|

=

n∑
m=⌈ n

3
⌉

|sd(Cn−1, m − 1)| + |sd(Cn−2, m − 1)| + |sd(Cn−3, m − 1)|

=

n−1∑
m=⌈ n

3
⌉−1

|sd(Cn−1, m)| +
n−2∑

m=⌈ n
3
⌉−1

|sd(Cn−2, m)| +
n−3∑

m=⌈ n
3
⌉−1

|sd(Cn−3, m − 1)|

= An−1 + An−2 + An−3

Table: SD(G, x) of different standard graphs and their roots are tabu-
lated in the table below

Graph Figure
Superior domination

polynomial SD(G, x)
Roots

Diamond
graph

v1

v4

v2 v3 x4 + 4x3 + 6x2 + 2x

x1 = 0,
x2 = −0.4563,

x3 = −1.7718 + 1.1151i,
x4 = −1.7718 − 1.1151i.

Claw
graph

v2 v3

v1

v4

x4 + 3x3 + 3x2 + x

x1 = 0,
x2 = −1,
x3 = −1,
x4 = −1.

Bull
graph

v3 v4

v5

v2v1

x5 + 3x4 + 3x3 + x2

x1 = 0,
x2 = −1,
x3 = −1,
x4 = −1.

Butterfly
graph

v3

v2

v5

v1

v4

x5 + 4x4 + 6x3 + 4x2 + x

x1 = 0,
x2 = −1,
x3 = −1,
x4 = −1,
x5 = −1.

(3,2)-Tadpole
graph

v2 v3
v4

v1

v5

x5 + 4x4 + 5x3 + 2x2

x1 = 0,
x2 = −1,
x3 = −2,
x4 = −1.

169



Tejaskumar R and A Mohamed Ismayil

Graph Figure
Superior domination

polynomial SD(G, x)
Roots

Kite graph
v3

v4

v1

v5

v2 x5 + 5x4 + 9x3 + 5x2 + x

x1 = 0,
x2 = −0.378 + 0.1877i,
x3 = −0.378 − 0.1877i,
x4 = −2.122 + 1.0538i,
x5 = −2.122 − 1.0538i.

(4,1)-Lollipop
graph

v3
v4

v1

v5

v2 x5 + 4x4 + 6x3 + 4x2 + x

x1 = 0,
x2 = −1,
x3 = −1,
x4 = −1,
x5 = −1.

House
graph

v2 v3

v1

v4 v5

x5 + 5x4 + 8x3 + 4x2 + x

x1 = 0,
x2 = −0.3076 + 0.3182i,
x3 = −0.3076 − 0.3182i,
x4 = −2.1924 + 0.5479i,
x5 = −2.1924 − 0.5479i.

House X
graph

v2 v3

v1

v4 v5

x5 + 5x4 + 8x3 + 5x2 + x

x1 = 0,
x2 = −1,
x3 = −1,

x4 = −0.382,
x5 = −2.618.

Gem
graph

v1 v2

v5

v3 v4
x5 + 4x4 + 4x3

x1 = 0,
x2 = −2.

Cricket
graph

v4 v5v3

v1 v2

x5 + 4x4 + 6x3 + 4x2 + x

x1 = 0,
x2 = −1,
x3 = −1,

x4 = −1, x5 = −1.

Pentatope
graph

v1

v4 v5

v2 v3
x5 + 5x4 + 10x3 + 10x2 + 5x

x1 = 0,
x2 = −0.691 = 0.9511i,
x3 = −0.691 − 0.9511,
x4 = −1.809 + 0.5878i,
x5 = −1.809 − 0.5878i.

Cross
graph

v3

v1

v2 v4

v5

v6

x6 + 5x5 + 9x4 + 7x3 + 2x2

x1 = 0,
x2 = −1,
x3 = −2,
x4 = −1,
x5 = −1.

170



Superior domination polynomial

Graph Figure
Superior domination

polynomial SD(G, x)
Roots

Fish
graph

v4

v2

v5

v1

v6

v3 x6 + 5x5 + 10x4 + 9x3 + 3x2

x1 = 0,
x2 = −1,
x3 = −1,

x4 = −32 +
√
3
2
i,

x5 = −32 −
√
3
2
i.

R
graph

v3 v4

v1

v5

v2

v6

x6 + 5x5 + 10x4 + 9x3 + 3x2

x1 = 0,
x2 = −1,
x3 = −1,

x4 = −32 +
√
3
2
i,

x5 = −32 −
√
3
2
i.

(2,3)-King
graph

v2 v3v1

v5v4 v6

x6 + 4x5 + 6x4 + 4x3 + x2

x1 = 0,
x2 = −1,
x3 = −1,
x4 = −1,
x5 = −1.

Antenna
graph

v2

v1

v3 v4

v5 v6

x6 + 4x5 + 5x4 + 2x3

x1 = 0,
x2 = −1,
x3 = −1,
x4 = −1.

3-prism
graph

v2

v3 v4

v1

v5 v6

x6 + 6x5 + 15x4 + 20x3

+15x2 + 6x

x1 = 0,
x2 = −2,

x3 = −0.5 + 0.866i,
x4 = −0.5 − 0.866i,
x5 = −1.5 + 0.866i,
x6 = −1.5 − 0.866i.

Moser
Spindle
graph

v1

v4 v5

v3v2

v6 v7

x7 + 4x6 + 6x5

+4x4 + x3

x1 = 0,
x2 = −1,
x3 = −1,
x4 = −1,
x5 = −1.

Cubical
graph

v3 v4

v5 v6

v1 v2

v8v7

x8 + 8x7 + 28x6 + 56x5

+70x4 + 48x3 + 16x2

x1 = 0,
x2 = −0.6714 + 0.5756i,
x3 = −0.6714 − 0.5756i,
x4 = −0.8352 + 1.4854i,
x5 = −0.8352 − 1.4854i,
x6 = −2.4934 + 0.9097i,
x7 = −2.4934 − 0.9097i.

Wagner
graph

v1

v8

v4 v5

v2

v7

v3

v6

x8 + 8x7 + 24x6

+32x5 + 16x4

x1 = 0,
x2 = −2,
x3 = −2,
x4 = −2,
x5 = −2.

171



Tejaskumar R and A Mohamed Ismayil

5 Conclusions
In this paper we introduced superior domination polynomial, this is a distance

based domination polynomial. Emphasis was given to the family of stars and
cycles. Formulas to find the coeffcients of the superior domination polynomials of
cycles and stars were stated and proved. These formulas helps us to calculate the
number of superior dominating sets of a specific desired cardinality for any given
value of n. The superior domination polynomial of different standard graphs and
their roots are calculated.

6 Acknowledgements
The authors express their gratitude to the managemanet- Ratio Mathematica

for their constant support towards the successful completion of this work. We wish
to thank the anonymous reviewers for the valuable suggestions and comments.

References
[1] S. Alikhani and Y. hock Peng. Introduction to domination polynomial of a

graph. arXiv preprint arXiv:0905.2251, 2009.

[2] F. Harary. Graph theory, Narosa Publ. House, New Delhi, 2001.

[3] T. Haynes. Domination in graphs: volume 2: advanced topics. Routledge,
2017.

[4] A. M. Ismayil and R. Tejaskumar. Eccentric domination polynomial of
graphs. Advances in Mathematics: Scientific Journal, 9:1729–1739, 2020.

[5] T. Janakiraman, M. Bhanumathi, and S. Muthammai. Eccentric domination in
graphs. International Journal of Engineering Science, Advanced Computing
and Bio-Technology, 1(2):1–16, 2010.

[6] K. Kathiresan and G. Marimuthu. Superior domination in graphs. Utilitas
Mathematica, 76:173, 2008.

[7] K. Kathiresan, G. Marimuthu, and S. West. Superior distance in graphs. Jour-
nal of combinatorial mathematics and combinatorial computing, 61:73, 2007.

[8] O. Ore. Path problems. Theory of graphs, 1962.

172