http://www.iaeme.com/IJMET/index.asp 1111 editor@iaeme.com
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
New Parameters on Inverse Domination
http://www.iaeme.com/IJMET/index.asp 1112 editor@iaeme.com
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βŒ‰ .
Now, 1-fd set and its inverse are mutually disjoint sets, the result 𝛾1𝑓𝑑′(𝑃𝑛)= βŒˆπ‘›+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
Jayasree T G and Radha Rajamani Iyer
http://www.iaeme.com/IJMET/index.asp 1113 editor@iaeme.com
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.
Theorem: If T is a tree of order 𝑛 β‰₯ 2, then 𝛾1𝑓𝑑′(𝑇) β‰₯ βŒˆπ‘›+1
3βŒ‰ and the equality will be
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
3βŒ‰ and the result follows.
New Parameters on Inverse Domination
http://www.iaeme.com/IJMET/index.asp 1114 editor@iaeme.com
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
sets. Hence 𝛾1𝑓𝑑
β€²(𝑇)β‰₯ βŒˆπ‘›+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.
Proposition: For 𝑛 β‰₯ 3, Ξ³2fd[T(Cn)] = ⌈2n
3βŒ‰ .
Theorem: Let Cn be a cycle with 𝑛 β‰₯ 3, vertices. Ξ³2fdβ€²[T(Cn)] = ⌈2n
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
T(Cn). So Ξ³2fdβ€²[T(Cn)] = ⌈2n
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
Jayasree T G and Radha Rajamani Iyer
http://www.iaeme.com/IJMET/index.asp 1115 editor@iaeme.com
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 Hv, 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.
Then π›Ύπ‘˜π‘“π‘‘β€²( 𝐺 π‘œ 𝐻)= { mΓ—Ξ³kfd(H) for k = 1
mΓ—Ξ³kfdβ€²(v+Hv) 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+Hv. As every π›Ύπ‘˜π‘“π‘‘- set of the graph 𝐺 π‘œ 𝐻,
contains the vertex 𝑣 ∈ 𝑉(𝐺), the π›Ύπ‘˜π‘“π‘‘β€²-set depends on v+Hv. This is true for all 𝑣 ∈ 𝑉(𝐺).
Hence π›Ύπ‘˜π‘“π‘‘β€²( 𝐺 π‘œ 𝐻)= m Γ— Ξ³kfdβ€²(v+Hv) for π‘˜ β‰₯ 2.
Corollary: In a graph 𝐺 π‘œ 𝐻, π›Ύπ‘˜π‘“π‘‘β€² exists only when π›Ύπ‘˜π‘“π‘‘(v+Hv) ≀ 𝑛
2, for the sub graph
v+Hv 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.