International Journal of Mechanical Engineering and Technology (IJMET)

Volume 10, Issue 03, March 2019, pp. 1111-1116. Article ID: IJMET_10_03_113
Available online at http://www.iaeme.com/ijmet/issues.asp?JType=IJMET&VType=10&IType=3
ISSN Print: 0976-6340 and ISSN Online: 0976-6359

© IAEME Publication Scopus Indexed

NEW PARAMETERS ON INVERSE

DOMINATION
Jayasree T G
Adi Shankara Institute of Engineering and Technology, Kalady, Kerala.

Radha Rajamani Iyer

Department of Mathematics, Amrita School of Engineering, Coimbatore,
Amrita Viswa Vidyapeetham, India.

ABSTRACT
A set D of vertices in a graph G(V, E) is a dominating set of G, if every vertex of V
not in D is adjacent to at least one vertex in D. A dominating set D of G(V, E)is a k –
fair dominating set of G, for 𝑘 ≥ 1 if every vertex in V – D is adjacent to exactly k
vertices in D. The k – fair domination number 𝛾𝑘𝑓𝑑 (𝐺) of G is the minimum cardinality
of a k – fair dominating set. In this article, we define the inverse of the k – fair
domination number and try to find it for some class of graphs.
Key words: Fair Domination, Inverse Domination, Inverse of k-fd set.
Mathematics Subject Classification: 05C69.
Cite this Article Jayasree T G and Radha Rajamani Iyer, New Parameters on Inverse
Domination, International Journal of Mechanical Engineering and Technology, 10(3),
2019, pp. 1111-1116.
http://www.iaeme.com/IJMET/issues.asp?JType=IJMET&VType=10&IType=3

1. INTRODUCTION
Let G(V, E) be a simple graph with vertex set V(G) and edge set E(G). The order and size
of G are denoted by n and m respectively. For graph theoretic terminology we refer to Gary
Chartrand and Ping Zhang [10] and Haynes et al. [11, 12]. For any vertex 𝑣 ∈ 𝑉, the open
neighborhood N(v) is the set {𝑢 ∈ 𝑉: 𝑢𝑣 ∈ 𝐸}, and the closed neighborhood N[v] is the set
𝑁(𝑣) ∪ {𝑣}. For any 𝑆 ⊆ 𝑉, 𝑁(𝑆) = ⋃𝑣∈𝑆 𝑁(𝑣) and 𝑁[𝑆] = 𝑁(𝑆) ∪ 𝑆.
A set D of vertices in a graph G(V, E) is a dominating set of G, if every vertex of V not in
D is adjacent to at least one vertex in D. Let D be a minimum dominating set of G. If V - D
contains a dominating set say D' is called an inverse dominating set with respect to D. The
inverse domination number 𝛾 ′ (𝐺) of G is the order of a smallest inverse dominating set of G.
A fair dominating set in graph G(V, E) is a dominating set D such that all vertices not in D
are dominated by same number of vertices from D, that is, every two vertices not in D has same

http://www.iaeme.com/IJMET/index.asp 1111 [email protected]

 New Parameters on Inverse Domination

number of neighbors in D. The fair domination number 𝛾𝑓𝑑 (𝐺) of G is the minimum cardinality
of an fd-set.
A dominating set 𝐷 ⊆ 𝑉(𝐺) is a k-fd set in G, if for every two distinct vertices 𝑢, 𝑣 ∈ 𝑉 −
𝐷 , |𝑁(𝑢) ∩ 𝐷| = | 𝑁(𝑣) ∩ 𝐷| = 𝑘. That is, every two distinct vertices not in D have exactly
k neighbors from D.
Now, let as define the inverse of k-fair dominating set and the inverse of k-fair domination
number as follows.
Definition: A set S of vertices in a graph G (V, E) is a k-fair dominating set of G, if every
vertex of V not in S is adjacent to exactly k vertices in S. Let S be a minimum k-fair dominating
set of G. If V - S contains a set say S ' called an inverse k-fair dominating set with respect to S,
if every vertex not in S ', is adjacent to at least k vertices in S '. The inverse k-fair domination
number 𝛾𝑘𝑓𝑑 ′(𝐺) of G is the order of a smallest inverse k-fair dominating set of G.
The following results are obvious.
′
1. For complete graph 𝐾𝑛 , 𝛾1𝑓𝑑 (𝐾𝑛 ) = 𝛾1𝑓𝑑 (𝐾𝑛 ) = 1 .
2. For complete bipartite graph 𝐾𝑚,𝑛 , 𝛾1𝑓𝑑 (𝐾𝑚,𝑛 ) = 𝛾1𝑓𝑑 ′ (𝐾𝑚,𝑛 ) = 2.
3. Let S be a 𝛾1𝑓𝑑 - set of a connected graph G. If 𝛾1𝑓𝑑 ′ - set exists, then G has at least two
vertices.
4. Let G be a connected graph with 𝛾(𝐺) = 𝛾1𝑓𝑑 (𝐺), then 𝛾1𝑓𝑑 ′ (𝐺) = 𝛾 ′ (𝐺).
5. Let G be a connected graph, then 𝛾𝑘𝑓𝑑 (𝐺) always depends on Δ(𝐺) and 𝛾𝑘𝑓𝑑 ′ (𝐺) depends
on 𝛿(𝐺). In other words, for k-fair domination, 𝑘 ≤ Δ and for inverse k-fair domination, 𝑘 ≤
𝛿.
𝑛
Lemma: Let 𝐾𝑛 be a complete graph of order n and let k be a positive integer with 𝑘 ≤ ⌊ 2⌋,
then 𝛾𝑘𝑓𝑑 ′ (𝐾𝑛 ) = 𝑘.
Proof: As we have, 𝐾𝑛 be a complete graph of order n, there exist k-fd sets for all 𝑘 ≤
(𝑛 − 1), with 𝛾𝑘𝑓𝑑 (𝐾𝑛 ) = 𝑘 for all 𝑛 ≥ 2. But 𝛾- set and 𝛾 ′ -set forms partition of vertex set
and in a complete graph, 2- distinct vertices are connected by edges, if there is a k-fd set, the
inverse set can have at the most (n - k) vertices. Hence for the maximum case, k = (n - k). In
𝑛 𝑛
other words, 𝑘 = 2 , or in general, 𝑘 ≤ ⌊ 2⌋. Then the result follows.

2. INVERSE DOMINATION IN 1-FD SETS

In this section we can find inverse fair domination in paths and trees, because in both cases we
can’t expect higher order inverse fair domination as 𝛿 = 1.
𝑛
Theorem: Let 𝑃𝑛 be a path with 𝑛 ≥ 2 vertices. Then 𝛾1𝑓𝑑 (𝑃𝑛 ) = ⌈ 3⌉ and 𝛾1𝑓𝑑 ′ (𝑃𝑛 ) =
𝑛+1
⌈ ⌉.
3
Proof: Let 𝑃𝑛 be a path with 𝑛 ≥ 2 vertices. To dominate n vertices exactly by one vertex,
𝑛
we need 3 vertices. This is true for any n, which is a multiple of 3. For each additional vertex
𝑛
we need one more vertex for fair domination. This lead to the result 𝛾1𝑓𝑑 (𝑃𝑛 ) = ⌈ 3⌉ .
𝑛+1
Now, 1-fd set and its inverse are mutually disjoint sets, the result 𝛾1𝑓𝑑 ′ (𝑃𝑛 ) = ⌈ 3 ⌉
follows.
Now, consider the case of trees. We refer Yair Caro, et.al [9] for the following notation.
A vertex of degree one is called a leaf and its neighbor is called a support vertex. Let 𝑆𝑇 , denote

http://www.iaeme.com/IJMET/index.asp 1112 [email protected]

 Jayasree T G and Radha Rajamani Iyer

the set of all support vertices of a tree T, and 𝐿𝑇 denotes the set of all leaves. A vertex adjacent
to at least two leaves in a tree T is known as strong support vertex of the tree. The graph obtained
by attaching a leaf to each vertex of a graph H is called corona of graph H and is denoted by
cor(H).
Observation: Every 𝛾1𝑓𝑑 ′ - set in a tree T contains all its leaves.
Proof: Already we have by [9], every 1-fd set contains all its strong support vertices. Also
we know that 𝛾1𝑓𝑑 set and 𝛾1𝑓𝑑 ′ set are mutually disjoint sets, the result follows.
𝑛
Observation: If T is the corona of a tree H and T has order n, then 𝛾1𝑓𝑑 ′ (𝑇) = .
2
Proof: If T is the corona of a tree of order n,[9], V(T) can be partitioned as 𝑆𝑇 and 𝐿𝑇 of
𝑛
cardinality 2 and these two sets are 𝛾1𝑓𝑑 - sets. Hence the result.
Observation: In a tree, if 𝛾𝑘𝑓𝑑 ′ exists, then k = 1.
Proof: Let T be a tree and let D be a fd-set. Then by the result of Yair Caro et.al.,[9], D is
a 1fd-set. But we have by the above observation, every 𝛾1𝑓𝑑 ′ set in a tree T contains all is leaves,
the result follows.
Proposition: Let T be a tree with 𝑛 ≥ 3 vertices with 𝑒 pendent vertices and 𝑏 supports.
′
Then 𝑏 ≤ 𝛾 ≤ 𝛾1𝑓𝑑 ≤ 𝛾1𝑓𝑑 ≤ 𝑒.
Theorem: Let S be a 𝛾1𝑓𝑑 - set of the tree T. Then T has a 𝛾1𝑓𝑑 ′ - set, if and only if the
following conditions satisfied.
T should be connected, that is, T contains no isolated vertices.
T has more than two end vertices.
|𝑆| ≤ |𝑉 − 𝑆|.
Proof: Given S be a 𝛾1𝑓𝑑 - set of the tree T, if T contains isolated vertex, say v, then 𝑣 ∈ 𝑆
and we can’t find a disjoined dominating set containing v. It contradicts our assumption that T
has a 𝛾1𝑓𝑑 ′ - set. Hence T should be connected.
Let as assume that T contains no isolated vertices. If T has only one end vertex, as T is
connected, T may contain cycles. And if T has no end vertices also assure the presence of cycles
in T. So these two cases contradict the assumption that T is a tree. Hence T must have more
than two end vertices.
Now let as assume that T has more than two end vertices. Then by the definition of S, all
the support vertices must belongs to S and all the leaves belongs to V - S. Hence, |𝑆| ≤ |𝑉 − 𝑆|.
Let |𝑆| ≤ |𝑉 − 𝑆|. We have to prove, T contains no isolated vertices. On the contrary, if
possible, assume that T is disconnected. Then each component contain 𝛾1𝑓𝑑 - set and if T contain
isolated vertex, they must be members of S and this contradicts our assumption that |𝑆| ≤
|𝑉 − 𝑆|. Hence, T must be connected.
Here we have, 1 ⟹ 2 ⟹ 3 ⟹ 1 . Hence the theorem.
𝑛+1
Theorem: If T is a tree of order 𝑛 ≥ 2, then 𝛾1𝑓𝑑 ′ (𝑇) ≥ ⌈ ⌉ and the equality will be
3
attained when T is a path 𝑃𝑛 .
Proof: Let T be a tree of order 𝑛 ≥ 2. A path is an acyclic graph or a tree by its construction
′
which has only two end vertices. If T is a path 𝑃𝑛 , then already we have the result, 𝛾1𝑓𝑑 (𝑃𝑛 ) =
𝑛+1
⌈ ⌉ and the result follows.
3

http://www.iaeme.com/IJMET/index.asp 1113 [email protected]

 New Parameters on Inverse Domination

If there exist more than two end vertices in a tree, then 𝐿𝑇 set contains more elements than
𝑆𝑇 . Hence in such cases, the inverse domination set contains more terms than the dominating
′ 𝑛+1
sets. Hence 𝛾1𝑓𝑑 (𝑇) ≥ ⌈ ⌉.
3
′
Theorem: If T is a tree of order 𝑛 ≥ 2, then 𝛾1𝑓𝑑 (𝑇) ≤ (𝑛 − 1) and the equality will be
attained when T is a star 𝑆1,(𝑛−1) .
Proof: Let T be a tree of order 𝑛 ≥ 2. If T is a star, 𝑆1,(𝑛−1), the central vertex of T is a 𝛾1𝑓𝑑
′ ′
- set, hence 𝛾1𝑓𝑑 (𝑇) = (𝑛 − 1). Also, this should be the maximum possible value for 𝛾1𝑓𝑑 (𝑇).
Hence the result.

3. INVERSE DOMINATION IN 2-FD SETS

Here we try to find inverse fair domination in total graph and square graph of cycles.
Proposition: In cycles, as every vertex is of degree 2, maximum expected value for k in
𝑛
𝛾𝑘𝑓𝑑 is 2 and 𝛾2𝑓𝑑 (𝐶𝑛 ) = ⌈ 2⌉, for 𝑛 ≥ 3.
𝑛
Proposition: Let 𝐶𝑛 be cycle with 𝑛 ≥ 4 vertices. Then 𝛾2𝑓𝑑 ′ (𝐶𝑛 ) = 2, if n is even. Also
for 𝑛 ≥ 4 and if n is odd, 𝛾2𝑓𝑑 ′ (𝐶𝑛 ) does not exists.
Now, we can consider the total graph of Cn . Let G(V,E) be a graph with vertex set V and
edge set E. The total graph of G, denoted by T(G) is defined as follows. The vertex set of T(G)
is 𝑉(𝐺) ∪ 𝐸(𝐺). Two vertices u, v in T(G) are adjacent if any one of the following holds: (i)
u, v are in V(G) and u is adjacent to v in G, (ii) u, v are in E(G) and u is adjacent to v in G, (iii)
u is in V(G), v is in E(G) and u, v are incident in G.
2n
Proposition: For 𝑛 ≥ 3, γ2fd [T(Cn )] = ⌈ 3 ⌉ .
2n
Theorem: Let Cn be a cycle with 𝑛 ≥ 3, vertices. γ2fd ′ [T(Cn )] = ⌈ 3 ⌉.
Proof: In Cn every vertex dominates exactly three vertices. Hence in T(Cn ) every vertex
dominates exactly 5 vertices because T(Cn ) is a 4- regular graph. Let as consider the graph
T(Cn ) as the union of two cycles Cn and Cn ′ joined by edges. Take any vertex v of Cn .
Beginning with v proceed cyclically about these two cycles in some direction to cover all the
2n vertices. Since T(Cn ) is a 4- regular graph, the vertices can partitioned into two sets say D
and D' such that they dominate every vertex of the graph exactly be two vertices. Hence D
become the two fair dominating set and D' be the inverse of two fair dominating set of the graph
2n
T(Cn ). So γ2fd ′ [T(Cn )] = ⌈ 3 ⌉ .
In this section we consider the square graph of the cycle Cn . The definition of square graph
of the cycle as follows. Let G (V, E) be a simple graph with vertex set V and edge set E. The
k-th power Gk of the graph G is another graph that has the same set of vertices, but in which
two vertices are adjacent when their distance in G is at most k. The Square graph G2 of graph
G is the graph that has the vertex set V in which two vertices are adjacent when their distance
in G is at most 2. Graph powers should be distinguished from the products of a graph with itself,
which (unlike powers) generally have many more vertices than the original graph.
𝑛
Proposition: Let Cn be cycle with 𝑛 ≥ 3 vertices. Then 𝛾2𝑓𝑑 [(𝐶𝑛 )2 ] = ⌈ 3⌉.
𝑛
Theorem: 𝛾2𝑓𝑑 ′ [(𝐶𝑛 )2 ] = ⌈ 3⌉ for 𝑛 ≥ 3.
Proof: Since Cn is two regular, (𝐶𝑛 )2 is a four regular graph. Hence every vertex of (𝐶𝑛 )2
dominates exactly five vertices. Take a set D consisting of any vertex v of (𝐶𝑛 )2 and every third
vertex of (𝐶𝑛 )2, starting with v and proceed cyclically in some direction. Then every vertex of

http://www.iaeme.com/IJMET/index.asp 1114 [email protected]

 Jayasree T G and Radha Rajamani Iyer

the graph is dominated exactly twice by the vertices of D. Same fashion, take another set say
D' in such a way that every second vertex u of (𝐶𝑛 )2 and fourth vertex of (𝐶𝑛 )2 in the same
direction. Then we get two sets D and D', both are disjoint sets but they dominate in a two fair
𝑛
dominating set of (𝐶𝑛 )2. Hence 𝛾2𝑓𝑑 ′ [(𝐶𝑛 )2 ] = ⌈ 3⌉.

4. INVERSE DOMINATION IN K-FD SETS

In this section we try to find the inverse of k-fair domination in corona of graphs. Corona of
graphs are defined as follows. Let G and H be graphs of order m and n respectively. The corona
of two graphs G and H is the graph 𝐺 𝑜 𝐻 obtained by taking one copy of G and m copies of H,
and joining the ith vertex of G to every vertex of the ith copy of H. We refer Emiliano C
Maravilla, et.at.,[1] for the following notation. For every 𝑣 ∈ 𝑉(𝐺), denote by H v , the copy of
H whose vertices are attached one by one to the vertex v. Denote by 𝑣 + 𝐻 𝑣 , the sub graph of
the corona 𝐺 𝑜 𝐻 corresponding to the join 〈{𝑣} + 𝐻 𝑣 〉.

Figure 1. Corona Product 𝐾5 𝑜 𝐾3 .

Theorem: Let G and H be non-trivial connected graphs of order m and n respectively.
m × γkfd (H) for k = 1
Then 𝛾𝑘𝑓𝑑 ′ ( 𝐺 𝑜 𝐻) = { .
m × γkfd ′ (v + H v ) for k ≥ 2
Proof: By the definition of 𝐺 𝑜 𝐻, each 𝑣 ∈ 𝑉(𝐺), is enough to form 𝛾1𝑓𝑑 - set, and hence
𝛾1𝑓𝑑 ( 𝐺 𝑜 𝐻) = m . Hence to form 𝛾1𝑓𝑑 ′ - set of minimum cardinality, we require 𝛾1𝑓𝑑 (𝐻)
members for each 𝑣 ∈ 𝑉(𝐺). Hence 𝛾1𝑓𝑑 ′ (𝐺 𝑜 𝐻) = 𝑚 × 𝛾1𝑓𝑑 (𝐻).
Now suppose, 𝑘 ≥ 2. Consider the sub graph v + H v . As every 𝛾𝑘𝑓𝑑 - set of the graph 𝐺 𝑜 𝐻,
contains the vertex 𝑣 ∈ 𝑉(𝐺), the 𝛾𝑘𝑓𝑑 ′ -set depends on v + H v . This is true for all 𝑣 ∈ 𝑉(𝐺).
Hence 𝛾𝑘𝑓𝑑 ′ ( 𝐺 𝑜 𝐻) = m × γkfd ′ (v + H v ) for 𝑘 ≥ 2.
𝑛
Corollary: In a graph 𝐺 𝑜 𝐻, 𝛾𝑘𝑓𝑑 ′ exists only when 𝛾𝑘𝑓𝑑 (v + H v ) ≤ 2, for the sub graph
v + H v of 𝐺 𝑜 𝐻.

5. CONCLUSION
In this work we define the inverse concept for k-fair domination number and find the same for
some class of graphs.

REFERENCES
[1] Emiliano C Maravilla, Rowena T Isla and Sergio R CanoyJr., k-Fair domination in the join,
corona, composition and Cartesian product of graphs, Applied Mathematical Sciences, Vol.
8, 2014, no.178, 8863-8874.

http://www.iaeme.com/IJMET/index.asp 1115 [email protected]

 New Parameters on Inverse Domination

[2] Gabriele Taentzer, Enrico Biermann, et.al., Generation of Sierpinski Triangles: A Case
Study for Graph Transformation Tools. Applications of Graph Transformations with
Industrial Relevance, pp. 514-539.
[3] Hamed Hatami, Pooya Hatami, Perfect dominating sets in the Cartesian products of prime
cycles, The Electronic J.Comb., 2007, 14(1).
[4] Jayasree T G, Radha R Iyer, The Results on the Inverse domination number of some class
of graphs, International Journal of Mechanical Engineering and Technology (IJMET)
Volume 9, Issue 1, January 2018, pp. 995 - 1004.
[5] M. M. Akbar Ali, S. Panauappan, Cycle multiplicity of total graph of Cn, Pn, and K{1,n},
International Journal of Engineering, Science and Technology, Vol.2, No.2, 2010, pp.54-
58.
[6] P.Jeyanthi, G. Hemalatha, B. Davvaz, Total Domination Subdivision Number in Strong
Product Graph, American Journal of Applied Mathematics and Statistics, 2014, Vol.2, No.4,
216-219.
[7] R. R. Iyer, A. Ganesan, The regular number of a graph, Journal of Discrete Mathematical
Sciences and Cryptography, 2012.
[8] T. Tamizh Chelvam, Sivagnanam Mutharasu, Efficient domination in Cartesian Products of
Cycles. Journal of Advanced Research in Pure Mathematics, Online ISSN 1943-2380,
Vol.3, Issue. 3, 2011, pp. 42-49.
[9] Yair Caro, Adriana Hansberg, Michael Henning, Fair domination in graphs, Discrete
Mathematics 312(2012), 2905-2914.
[10] Gary Chartrand, Ping Zhang, Introduction to Graph Theory, Tata McGraw-Hill Edition
(2006).
[11] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Domination in Graphs: Advanced Topics.
Marcel Dekker, New York (2000).
[12] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in
Graphs. Marcel Dekker, New York (2000).

http://www.iaeme.com/IJMET/index.asp 1116 [email protected]