1. Introduction
By a graph
, we mean a finite undirected graph with neither loops nor multiple edges. The order and the size of G are denoted by n and m respectively, the open neighborhood
and the closed neighborhood
. The degree of a vertex v in G is
. Let G and H be any two graphs with vertex sets
,
and edge sets
,
, respectively. Then, the union
is the graph whose vertex set is
and edge set is
. For graph theoretic terminology, we refer to [1] and [2] .
A set D of vertices in a graph
is a dominating set if every vertex in
is adjacent to some vertex in D. The domination number
is the mini- mum cardinality of a dominating set. An excellent treatment of the fundamentals of domination is given by Hayens et al. [3] . A survey of several advanced topics in domi- nation is given in the book edited by Haynes et al. [4] .
The injective domination of graphs has been introduced by A.Alwardi et al. [5] . For a graph G, a subset D of
is called an injective dominating set (Inj-dominating set) if for every vertex
there exists a vertex
such that
, where
is the number of common neighborhood between the vertices u and v. The minimum cardinality of such dominating set is denoted by
and is called the injective domination number(Inj-domination number) of G. The Inj-neighborhood of a vertex
denoted by
is defined as
. The cardinality of
is called the injective degree of the vertex u and is denoted by
in G and
.
A subset D of V is called equitable dominating set of G if every vertex
adjacent to at least one vertex
and
. The minimum cardinality of such a dominating set is denoted by
and is called equitable domination number of G [6] . Equitable domination has interesting applications in the context of social networks. In a network, nodes with nearly equal capacity may interact with each other in a better way.
The importance of injective and equitable domination of graphs motivated us to introduce the injective equitable domination of graphs which mixes the two concepts.
As there are a lot of applications of domination, in particular the injective and equitable domination, we are expecting that our new concept has some applications.
2. The Injective Equitable Dominating Set
Definition 1 A subset D of
is called injective equitable dominating set (Inj- equitable dominating set) if for every vertex
there exists a vertex
such that u is adjacent to v and
. The minimum cardinality of such a dominating set is denoted by
and is called the Inj-equitable domination number of G. A
-set of G is the minimum dominating set of G.
It is easy to see that any Inj-equitable dominating set in a graph G is also a domi- nating set, and then
and
if and only if
.
In the following propostion the Inj-equitable domination number of some standard graphs are determined.
Proposition 1
1) For any complete graph
, ![]()
2) For any path
, with n vertices, ![]()
3) For any cycle
on n vertices,
.
4) For any complete bipartite graph
, where
,
![]()
5) For any wheel graph
.
Definition 1 motivated us to define the inherent Inj-equitable graph of any graph G as follows:
Definition 2 Let
be a graph. The inherent Inj-equitable graph of G, denoted by
, is defined as the graph with vertex set
and two vertices u and v are adjacent in the
if and only if u and v are adjacent in G and
.
Theorem 2: For any graph
, ![]()
Proof. Since any Inj-equitable dominating set of
is a dominating set of
, then
. Now, let
be any
-dominating set of
. Then for any
, there exists
such that u and v are adjacent in
. So,
. Therefore, D is Inj-equitable dominating set of G. Then,
. Hence,
.
Definition 3 The Inj-equitable neighborhood of
,
, is defined as
![]()
The cardinality of
is called the Inj-equitable degree of u and is denoted by
. The maximum and minimum Inj-equitable degree of a vertex in G are denoted respectively by
and
. That is,
![]()
![]()
Definition 4 For any graph G, an edge
is called Inj-equitable edge if
and we say u is Inj-equitable adjacent to v or u is Inj-equitable dominate v.
Proposition 3 For any graph
,
, where
is the number of Inj-equitable edges in G.
Proof. Let G be a graph and let H be the Inj-equitable graph of G. Then
, where q is the number of edges in H. Since the number of edges in
H is the number of Inj-equitable edges in G, then q equals
. Also,
in G
is equal to
in H. Hence,
.
Definition 5 Let
be a graph. A vertex
is called Inj-equitable isolated vertex if
. The set of all Inj-equitable isolated vertices is denoted by
. Hence
for every Inj-equitable dominating set D, where I is the set of isolated vertices.
Definition 6 A graph G is called Inj-equitable totally disconnected graph if it has no Inj-equitable edge.
Theorem 4 For any graph G with n vertices,
. Further,
if and only if there exists at least one vertex v in G such that
.
if and only if G is Inj-equitable totally disconnected graph.
Proof. It is obviously that
. Also, for any graph
,
is an injective equitable dominating set. Therefore,
. Hence,
.
Now, we want to prove that
if and only if there exists at least one vertex v in G such that
. Suppose that
and
is a
- set. So, for all
,
and
. Hence,
.
conversely, suppose that there exists at least one vertex v in G such that
. Then,
is an Inj-equitable dominating set. Hence,
.
To prove that
if and only if G is Inj-equitable totally disconnected graph, suppose that G is Inj-equitable totally disconnected graph. So, all the vertices are Inj-equitable isolated. Hence,
.
Conversely, suppose that G has at least one Inj-equitable edge, say
. So,
. Therefore,
is an Inj-equitable dominating set, and so,
contradicts that
. Hence, G is Inj-equitable totally dis- connected graph.
Proposition 5 If a graph G has no Inj-equitable isolated vertices, then
![]()
In the following theorem, we present the graph for which
and
are equal.
Theorem 6 Let G be a graph such that any two adjacent vertices contained in a triangle or G is regular triangle-free graph. Then,
.
Proof. Suppose that G is a regular triangle-free graph and D is a
-set of G. Then
. Let u and v be any two adjacent vertices in G. Then
. Therefore,
. Since G is regular,
. So,
. Therefore, D is an Inj-equitable domi- nating set. So that,
. But
. Hence,
.
Let G be a graph such that any two adjacent vertices contains in a triangle. It is clear that for any
,
. So,
. By the same way of the proof of regular triangle-free graph we can prove that
.
Lemma 1 For any two graphs
and
,
.
Proof. Let
and let
and
be the minimum Inj-equitable domi- nating set of
and
, respectively, such that
and
. Now, it is obviously that
is an Inj-equitable dominating set of
. Therefore,
![]()
That is,
(1)
To prove
by contradiction. Let
be the minimum Inj-equitable dominating set of G such that
. Let
. Then there exist
and
, where
is the mini- mum Inj-equitable dominating set of
and
is the minimum Inj-equitable dominating set of
and either
or
which is a contradiction. Hence
(2)
From 1 and 2, we get
![]()
By mathematical induction, we can generalize Lemma 1 as follows:
Proposition 7 Let
be a graph. Then ![]()
Theorem 8 Let G be a graph with
vertices. Then
if and only if
, where H is Inj-equitable totally disconnected graph.
Proof. Let G be a graph with
vertices and let
. By Theorem 2,
which implies that
will be of the form
. By the Definition 2, all the edges of G are not Inj-equitable edge except one edge. Therefore,
.
Conversely, let
where H is an Inj-equitable totally disconnected graph. By Lemma 1,
.
Definition 7 An Inj-equitable dominating set D is said to be a minimal Inj-equitable dominating set if no proper subset of D is an Inj-equitable dominating set. A minimal Inj-equitable dominating set D of maximum cardinality is called
-set and its cardinality, denoted by
, is called upper Inj-equitable domination number.
The following theorem gives the characterization of the minimal Inj-equitable domi- nating set .
Theorem 9 An Inj-equitable dominating set D is minimal if and only if for every vertex
one of the following holds:
1) u is not Inj-equitable adjacent to any vertex in D.
2) There exists a vertex
such that
.
Proof. Suppose that D is minimal Inj-equitable dominating set and suppose that
. Then,
is not Inj-equitable dominating set. Therefore, there exists a vertex
which is not Inj-equitable adjacent to any vertex in
. Then, either
or
. If
, then u is not Inj-equitable adjacent to any vertex in D. If
, then
and not Inj-equitable adjacent to any vertex in
. But V is Inj-equitable dominated by D. So, V is Inj-equitable adjacent only to vertex u in D. Hence,
.
Conversely, suppose that D is an Inj-equitable dominating set and for every vertex
one of the two conditions holds. We want to prove that D is minimal. Suppose D is not minimal. Then there exists a vertex
such that
is an Inj- equitable dominating set. Therefore, there exists
such that v Inj-equitable adjacent to u. Therefore, u does not satisfy (i). Also, if
is Inj-equitable domi- nating set, then every vertex
is Inj-equitable adjacent to at least one vertex in
. So, condition (ii) does not hold which is a contradiction. Hence, D is a minimal Inj-equitable dominating set.
Theorem 10 A graph G has a unique minimal Inj-equitable dominating set if and only if the set of all Inj-equitable isolated vertices forms an Inj-equitable dominating set.
Proof. Let G has a unique minimal Inj-equitable dominating set D and let
. Since v is not an Inj-equitable isolated,
is an Inj-equitable domi- nating set. Therefore, there exists a minimal Inj-equitable dominating set
and
, which contradicts that G has a unique minimal Inj-equitable dominating set. Hence,
.
Conversely, let
forms an Inj-equitable dominating set. Then it is clear that G has a unique minimal Inj-equitable dominating set.
Theorem 11 If G is a graph has no Inj-equitable isolated vertices, then the com- plement
of any minimal Inj-equitable dominating set S is also an Inj-equitable dominating set.
Proof. Let S be any minimal Inj-equitable dominating set of G and
is not Inj- equitable dominating set. So, there exist at least one vertex
which is not Inj- equitable dominated by any vertex in
. Since G has no Inj-equitable isolated vertices, the vertex u must be Inj-equitable dominated by at least one vertex in
. Thus,
is an Inj-equitable dominating set of G, which contradicts the mini- mality of S. Hence,
is an Inj-equitable dominating set.
Theorem 12 For any graph with n vertices
![]()
Proof. Let S be a
-set of G. Then for all
,
![]()
Thus,
![]()
Now,
![]()
Therefore,
![]()
Hence,
![]()
Definition 8 Let
. A subset S of
is called an Inj-equitable in- dependent set if for any
,
for all
. The maximum car- dinality of an Inj-equitable independent set is denoted by
.
Definition 9 An Inj-equitable independent set S is called maximal if any vertex set properly containing S is not Inj-equitable independent set. The lower Inj-equitable independent number
is the minimum cardinality of the maximal Inj-equitable independent set.
Theorem 13 Let S be a maximal Inj-equitable independent set. Then S is a minimal Inj-equitable dominating set.
Proof. Let S be a maximal Inj-equitable independent set. Let
. If
for every
, then
is an Inj-equitable independent set, a contradiction to the maximality of S. So,
for some
. Hence, S is ann Inj-equitable dominating set. Since for any
,
for every
, either
or
for all
. Therefore, S is minimal Inj-equitable dominating set.
Theorem 14 For any graph G,
![]()
3. Injective Equitable Domatic Number
The maximum order of a partition of a vertex set V of a graph G into dominating sets is called the domatic number of G and is denoted by
[7] . In this section we pre- sent a few basic results on the Inj-equitable domatic number of a graph.
Definition 10 An Inj-equitable domatic partition of a graph G is a partition
of
in which each
is Inj-equitable dominating set of G. The Inj-equitable domatic number is the maximum order of an Inj-equitable domatic parti- tion and is denoted by
.
Example 1 For the graph G given in Figure 1,
is an Inj-equitable domatic partition of maximum order. Therefore, the Inj-equitable domatic number of G is
.
Proposition 15
1) For any path
with
,
.
2) For any cycle
with
, ![]()
3) For any complete graph
,
.
4) For any complete bipartite graph
, where
,
![]()
Proposition 16 For any graph G,
, where
is the domatic number of G.
Proof. Since any partition of V into Inj-equitable dominating set is also partition of V into dominating set,
.
4. Conclusions
In this paper, we introduced the Inj-equitable domination of graphs and some other related parameters like Inj-equitable independent number, uper Inj-equitable domi- nation number and domatic Inj-equitable domination number.
There are many other related parameters for future studies like connected Inj- equitable domination, total Inj-equitable domination, independent Inj-equitable domi- nation, split Inj-equitable domination and clique Inj-equitable domination.