See discussions, stats, and author profiles for this publication at: [Link]

net/publication/343376769

Co-Even Domination In Graphs

Article in International Journal of Control and Automation · January 2020

CITATIONS READS

24 1,225

2 authors:

Manar Makki Shaalan Ahmed A Omran

University of Babylon University of Babylon
4 PUBLICATIONS 49 CITATIONS 97 PUBLICATIONS 668 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Ahmed A Omran on 01 August 2020.

The user has requested enhancement of the downloaded file.

 International Journal of Control and Automation
Vol. 13, No. 3, (2020), pp. 330-334

Co-Even Domination In Graphs

Manar M. Shalaan1 and Ahmed A. Omran2
1&2
Department of Mathematics, College of Education for Pure Science
University of Babylon, Babylon, Iraq
1
manarmacki92@[Link], 2 [Link]@[Link]

Abstract
The aim of this paper is to introduce a new domination parameter in the graphs it is called co-
even domination number denoted by 𝑐𝑜𝑒 (𝐺). We will touch only a few aspects of the theory to
this definition. Some properties and boundaries of this definition are introduced. Furthermore,
some properties for some standard graphs and complement graphs are discussed, such as path,
cycle, complete, complete bipartite, star, regular, and wheel.
Mathematical subject classification: 05C69
Keywords: Graph, complement of graph, co-even domination number, co-even dominating set.

1. Introduction
Through this work, all graphs are considered finite, simple, and undirected. On a graph 𝐺 =
(𝑉, 𝐸) with vertex set 𝑉 (𝐺) and edge set 𝐸(𝐺). For each vertex 𝑣 ∈ 𝑉(𝐺), the set 𝑁𝐺 (v) =
{𝑢 ∈ 𝑉(𝐺 ): 𝑢𝑣 ∈ 𝐸(𝐺)} refers to the open neighborhood of 𝑣 and the set 𝑁𝐺 [𝑣] = 𝑁𝐺 (v) ∪ {𝑣}
refers to the closed neighborhood of 𝑣 in 𝐺. The degree of 𝑣, denoted by 𝑑𝑒𝑔(𝑣), is the cardinality
of 𝑁𝐺 (𝑣). An isolated, a pendant vertex is a vertex of degree zero and one respectively. The
minimum and maximum degree (𝐺) and Δ(𝐺), respectively. In case where Δ(𝐺) = 𝛿(𝐺), 𝐺 is called
a regular graph [4], [6]. For new types of parameter of graph domination and refer to [1-3,8-10].
A subset D of V is called a dominating set of G if every vertex not belong to the set D is adjacent
to at least one vertex u: u ∈ D. A dominating set D of G is minimal if has no proper a dominating
set in G. MDS(G)refers to all minimal dominating sets of a graph G. If D = min{|Di |, Di ∈
MDS(G) } where |Di |is the cardinal of the set Di , then D is called the domination number of G and
is denoted by γ(G) [5], [7].
Now, a new domination parameter in the graphs it is called co-even domination number denoted
by 𝑐𝑜𝑒 (𝐺) is definition below. Some properties for some standard graphs of co-even domination
are been discussed. Also, some bounds for γcoe (G) are obtained and characterized the graphs
obtaining those bounds.

2. Co-even Domination number

Definition 2.1. Let 𝐺 be a graph and 𝐷 is a dominating set, the set 𝐷 is called co-even
dominating set if, deg(𝑣) is even number for all 𝑣 ∈ 𝑉 − 𝐷.
Definition 2.2. Consider 𝐺 be a graph and 𝐷 is a co-even dominating set ,then 𝐷 is called a
minimal co-even dominating set if has no proper subset 𝐷́ D is a co-even dominating of G
. Take us MCEDS(G) refers to all minimal co- even dominating sets of a graph G.

Definition 2.3. The set D is called the co-even domination number if

𝐷 = 𝑚𝑖𝑛{|𝐷𝑖 |, 𝐷𝑖 ∈ 𝑀𝐶𝐸𝐷𝑆(𝐺) }, and is denoted by 𝛾 coe (𝐺).
Proposition 2.4. Let 𝐺 = (𝑛, 𝑚) be a graph and 𝐷 is a co-even dominating set, then
1. All vertices of odd or zero degrees belong to every co-even dominating set.
2. 𝑑𝑒𝑔(𝑣) ≥ 2, 𝑓𝑜𝑟𝑎𝑙𝑙 𝑣 ∈ 𝑉 − 𝐷

330
ISSN: 2005-4297 IJCA
Copyright ⓒ 2020 SERSC
 International Journal of Control and Automation
Vol. 13, No. 3, (2020), pp. 330-334

𝑛, 𝑖𝑓 𝑟 𝑖s 𝑜𝑑𝑑
3. If 𝐺 is r- regular graph then 𝛾𝑐𝑜𝑒 (𝐺 ) = { }.
𝛾(𝐺 ), 𝑖𝑓 𝑟 𝑖s even
4. 𝛾 (𝐺 ) ≤ 𝛾𝑐𝑜𝑒 (𝐺 ).
Proof. It is clear that from the definition of co-even dominating set. □
Proposition 2.5. If 𝐺 be a graph of order n, then 1 ≤ 𝛾𝑐𝑜𝑒 (𝐺 ) ≤ 𝑛.
Proof. If graph 𝐺 has a vertex of degree 𝑛 − 1 and vertices of even degree to each other then,
in this case, the lower bound is obtained. The upper bound has appeared when the degrees
of all vertices are odd or zero, according to proposition 2.4(1).
Proposition 2.6. If 𝐺 = (𝑛, 𝑚)is a graph has co-even domination number 𝛾𝑐𝑜𝑒 , then
𝑛−𝛾 𝑛(𝑛−1)
(𝑛 − 𝛾𝑐𝑜𝑒 ) + ⌈ 𝑐𝑜𝑒 ⌉ ≤ 𝑚 ≤ .
2 2

Proof. Let 𝐷 be a 𝛾𝑐𝑜𝑒 - set, then all the vertices in 𝑉 − 𝐷 have at least one edge that joins
each of them with D. Therefore, there are at least 𝑛 − 𝛾𝑐𝑜𝑒 edges. Furthermore, these vertices
𝑛−𝛾
must be of even degree, so the minimum number of edges to add to 𝑛 − 𝛾𝑐𝑜𝑒 is ⌈ 2𝑐𝑜𝑒 ⌉. This
case occurs when the induced subgraph generated by 𝑉 − 𝐷 (〈𝑉 − 𝐷〉) is isomorphic to the
match graph. This means that the edges are independent in 〈𝑉 − 𝐷〉 when 𝑛 − 𝛾𝑐𝑜𝑒 is even.
Now, if 𝑛 − 𝛾𝑐𝑜𝑒 is odd, similarly, the minimum number of edges occurs when every two
vertices are joined pairwise. One vertex remains, therefore, the minimum number of edges
will be obtained when this vertex joins with another vertex in 𝐷, since if we join this vertex
with another vertex, let's say w in 𝑉 − 𝐷 the degree of w becomes odd. Therefore, that we
𝑛−𝛾
must add a new edge. Thus, the lower bound of edges is (𝑛 − 𝛾𝑐𝑜𝑒 ) + ⌈ 𝑐𝑜𝑒 ⌉. 2

It is clear that the upper limit is obtained when the graph is completed. Thus, the result is
obtained.
Observation 2.7.
𝑛
1. 𝛾𝑐𝑜𝑒 (𝐶𝑛 ) = ⌈ ⌉ , 𝑤ℎ𝑒𝑟𝑒 𝐶𝑛 𝑖𝑠 𝑎 𝑐𝑦𝑐𝑙𝑒 𝑜𝑓 𝑜𝑟𝑑𝑒𝑟 𝑛.
3
1, 𝑖𝑓 𝑛 ≡ 1 (𝑚𝑜𝑑 2)
2. 𝛾𝑐𝑜𝑒 (𝐾𝑛 ) = { }. , 𝑤ℎ𝑒𝑟𝑒 𝐾𝑛 𝑖𝑠 𝑎 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒 𝑜𝑓 𝑜𝑟𝑑𝑒𝑟 𝑛; 𝑛 ≥ 3
𝑛, 𝑖𝑓 𝑛 ≡ 0 (𝑚𝑜𝑑 2)
Proof. By proposition 2.4(3). □
Proposition 2.8. If G is a star graph or wheel graph of order n,( 𝑛 ≥ 3, 𝑛 ≥ 4 respectively) ,
𝑛 − 1, 𝑖𝑓 𝑛 ≡ 1 (𝑚𝑜𝑑 2)
then 𝛾𝑐𝑜𝑒 (𝐺 ) = { }.
𝑛, 𝑖𝑓 𝑛 ≡ 0 (𝑚𝑜𝑑 2)
Proof. Let 𝐺 be a star or wheel graph of order 𝑛, then by proposition 2.4(2), all pendant
vertices in star and all vertices that lie on the cycle of the wheel belong to every co-even
dominating set 𝐷, since that the degree of all these vertices is odd. Therefore, the remaining
vertex of each graph is the center. So, two cases are discussed as follows.
Case 1. If 𝑛 ≡ 1 (𝑚𝑜𝑑 2), then the degree of center vertex is even. Therefore, we place this
vertex in set 𝑉 − 𝐷. Thus, 𝛾𝑐𝑜𝑒 (𝐺 ) = 𝑛 − 1.
Case 2. If 𝑛 ≡ 0 (𝑚𝑜𝑑 2), then the degree of center vertex is odd. Again, by Proposition
2.4(2), this vertex belongs to every co-even dominating set. Thus, 𝛾𝑐𝑜𝑒 (𝐺 ) = 𝑛. □
Proposition 2.9. If G is a complete bipartite graph 𝐾𝑚,𝑛 , then 𝛾𝑐𝑜𝑒 (𝐺 ) =
2, 𝑖𝑓 𝑛 𝑎𝑛𝑑 𝑚 𝑎𝑟𝑒 𝑒𝑣𝑒𝑛
{ 𝑛, 𝑖𝑓 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛 𝑎𝑛𝑑 𝑚 𝑖𝑠 𝑜𝑑𝑑 }.
𝑛 + 𝑚, 𝑖𝑓 𝑏𝑜𝑡ℎ 𝑛 𝑎𝑛𝑑 𝑚 𝑎𝑟𝑒 𝑜𝑑𝑑
Proof. Suppose that 𝑉1 and 𝑉2 are the bipartite sets of the graph 𝐺 of order 𝑛 and 𝑚,
respectively. Then there are three cases that depend on 𝑛 and 𝑚 as follows.

331
ISSN: 2005-4297 IJCA
Copyright ⓒ 2020 SERSC
 International Journal of Control and Automation
Vol. 13, No. 3, (2020), pp. 330-334

Case1. If 𝑛 𝑎𝑛𝑑 𝑚 are even, then let 𝑢 ∈ 𝑉1 and 𝑣 ∈ 𝑉2 . It is clear that 𝑢 𝑎𝑛𝑑 𝑣 dominate
all other vertices in the graph as well, all other vertices with even degree. We cannot
dominate this graph by a vertex. Therefore, 𝑐𝑜𝑒 (𝐺 ) = 2.
Case 2. If 𝑚 is odd and 𝑛 is even, then, according to Proposition 2.4(1) all the vertices in
set 𝑉1 belong to every co-even dominating set. Therefore,𝛾𝑐𝑜𝑒 (𝐺 ) = 𝑛, since all vertices in
the set 𝑉2 have even degree.
Case 3. If 𝑛 and 𝑚 are odd, then by proposition 2.4(1) all vertices in the sets 𝑉1 and 𝑉2 belong
to each co-even dominating set. Thus, 𝛾𝑐𝑜𝑒 (𝐺 ) = 𝑚 + 𝑛.
Therefore, from all the previous cases, the result is obtained. □
Proposition 2.10. If 𝐺 is a path graph of order 𝑛, then
𝑛−4
𝛾𝑐𝑜𝑒 (𝐺 ) = 2 + ⌈ 3
⌉.

Proof. Let 𝑣1 , 𝑣2 , … , 𝑣𝑛 be the vertices of the path. By proposition 2.4(1) the two pendant
vertices 𝑣1 and 𝑣𝑛 lie in each co-even dominating set. These vertices dominate the support
𝑛−4
vertices 𝑣2 and 𝑣𝑛−1 . Now, let 𝐷1 = {𝑣4+3𝑘 , 𝑘 = 0,1, … , ⌈ 3 ⌉ − 1}. It is clear that 𝐷1 is a
minimum co-even dominating set to the induced subgraph 〈𝑣3 , 𝑣4 , … , 𝑣𝑛−2 〉, Thus, 𝛾𝑐𝑜𝑒 (𝐺 ) =
𝑛−4
2 + ⌈ ⌉.
3

3. Co-even dominating set in the complement of a graph.

Proposition 3.1. If 𝐺 is r- regular graph then 𝛾𝑐𝑜𝑒 ( 𝐺̅ ) =
𝑛, 𝑖𝑓 𝑟 𝑖s 𝑜𝑑𝑑(𝑒𝑣𝑒𝑛)𝑎𝑛𝑑 𝑛 𝑖s 𝑜𝑑𝑑(𝑒𝑣𝑒𝑛)
{ }
𝛾(𝐺 ), 𝑖𝑓 𝑟 𝑖s 𝑜𝑑𝑑(𝑒𝑣𝑒𝑛)𝑎𝑛𝑑 𝑛 𝑖s 𝑒𝑣𝑒𝑛(𝑜𝑑𝑑)
Proof. There are four cases that depend on 𝑟 and 𝑛 as follows.
Case 1. If 𝑟 and 𝑛 are odd or even together, then the degree of each vertex in 𝐺̅ is odd. Thus, all
vertices belong to co-even dominating set according to Proposition 2.4(1), so 𝛾𝑐𝑜𝑒 ( 𝐺̅ ) = 𝑛.
Case 2. If 𝑟 is odd (even) and 𝑛 is even (odd), respectively, then the degree of each vertex in 𝐺̅
is even. Therefore, 𝛾𝑐𝑜𝑒 ( 𝐺̅ ) = 𝛾(𝐺 ). Therefore, from the two previous cases, the result is obtained.
Proposition 3.2. if 𝐺 is a path graph of order 𝑛, then
𝑛 − 2 , 𝑖𝑓 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛
𝛾𝑐𝑜𝑒 (̅̅̅
𝑃𝑛 ) = { }.
2 , 𝑖𝑓 𝑛 𝑖𝑠 𝑜𝑑𝑑
Proof. Two cases are discussed as follows.
Case 1. If 𝑛 is even, then the degree of all vertices in ̅̅̅
𝑃𝑛 are odd, except for the pendant two
vertices. Therefore, according to proposition 2.4(1) 𝛾𝑐𝑜𝑒 (̅̅̅
𝑃𝑛 ) = 𝑛 − 2.
Case 2. If 𝑛 is odd, then the degree of all vertices in ̅̅̅
𝑃𝑛 are even except for the pendant two
vertices. Also, the pendant vertices in 𝑃𝑛 have dominated all vertices in ̅̅̅
𝑃𝑛 . Therefore, 𝛾𝑐𝑜𝑒 (̅̅̅
𝑃𝑛 ) =
2.
Therefore, from the two previous cases, the result is obtained. □
Proposition 3.3. . If 𝐺 is a cycle graph of order 𝑛, then
𝑛 , 𝑖𝑓 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛 𝑜𝑟 𝑛 = 3
𝛾𝑐𝑜𝑒 (̅̅̅
𝐶𝑛 ) = { }.
2 , 𝑖𝑓 𝑛 𝑖𝑠 𝑜𝑑𝑑; 𝑛 ≠ 3
Proof. Three cases are discussed as follows.

332
ISSN: 2005-4297 IJCA
Copyright ⓒ 2020 SERSC
 International Journal of Control and Automation
Vol. 13, No. 3, (2020), pp. 330-334

Case 1. If 𝑛 = 3, then ̅̅̅

𝐶3 ≡ ̅̅̅
𝐾3 , therefore 𝛾𝑐𝑜𝑒 (̅̅̅
𝐶𝑛 ) = 3, according to proposition 2.4(1).
Case 2. If 𝑛 is even, then the degree of all vertices in ̅̅̅
𝐶𝑛 are odd. Therefore, according to
proposition 2.4(1) 𝛾𝑐𝑜𝑒 (̅̅̅
𝐶𝑛 ) = 𝑛.
Case 3. If 𝑛 is odd; 𝑛 ≠ 3, then the degree of all vertices in ̅̅̅
𝐶𝑛 are even. Also, any adjacent vertices
in 𝐶𝑛 have dominated all vertices in ̅̅̅
𝐶𝑛 . Therefore, 𝛾𝑐𝑜𝑒 (̅̅̅
𝐶𝑛 ) = 2.
Therefore, from the three previous cases, the result is obtained. □
Proposition 3.4. If 𝐺 is a wheel graph of order 𝑛, then
𝑛, 𝑖𝑓 𝑛 𝑖𝑠 𝑜𝑑𝑑 𝑜𝑟 𝑛 = 4
𝛾𝑐𝑜𝑒 (̅̅̅̅
𝑊𝑛 ) = { }.
3, 𝑖𝑓 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛; 𝑛 ≠ 4
Proof. Three cases are discussed as follows.
Case 1. If 𝑛 = 4, then ̅̅̅̅
𝑊4 ≡ ̅̅̅
𝐾4 , therefore 𝛾𝑐𝑜𝑒 (̅̅̅̅
𝑊𝑛 ) = 4, according to proposition 2.4(1).
Case 2. If 𝑛 is odd, then the degree of all vertices in ̅̅̅̅
𝑊𝑛 are odd except the center vertex which
degree is zero. Therefore, according to proposition 2.4(1) 𝛾𝑐𝑜𝑒 (̅̅̅̅
𝑊𝑛 ) = 𝑛.
Case 3. If 𝑛 is even; 𝑛 ≠ 4, then the degree of all vertices in ̅̅̅̅
𝑊𝑛 are even except the center vertex
which degree is zero. Therefore, by using Proposition 3.3. we get 𝛾𝑐𝑜𝑒 (̅̅̅̅̅̅
𝐶𝑛−1 ) = 2, so, 𝛾𝑐𝑜𝑒 (̅̅̅̅
𝑊𝑛 ) =
3.
Therefore, from the three previous cases, the result is obtained. □
Proposition 3 .5. If G is a star graph of order 𝑛, then
2, 𝑖𝑓 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛
𝛾𝑐𝑜𝑒 (̅̅̅
𝑆𝑛 ) = { }.
𝑛, 𝑖𝑓 𝑛 𝑖𝑠 𝑜𝑑𝑑
Proof. If 𝐺 ≡ 𝑆𝑛 , then ̅̅̅
𝑆𝑛 ≡ 𝐾𝑛−1 ∪ 𝐾1 . Therefore, by using Proposition 2.4(2), the result is
obtained. □
Observation 3.6. If G is a complete graph of order 𝑛, then 𝛾𝑐𝑜𝑒 (̅̅̅̅
𝐾𝑛 ) = 𝑛.
proof. It is obvious. □
Proposition 3.7. If G is a complete bipartite graph of order 𝑛𝑚, then
2, 𝑖𝑓 𝑚 𝑎𝑛𝑑 𝑛 𝑎𝑟𝑒 𝑜𝑑𝑑
̅̅̅̅̅̅
𝛾𝑐𝑜𝑒 (𝐾 𝑚,𝑛 ) = { 𝑚 + 1, 𝑖𝑓 𝑚 𝑖𝑠 𝑒𝑣𝑒𝑛 𝑎𝑛𝑑 𝑛 𝑖𝑠 𝑜𝑑𝑑}
𝑚 + 𝑛, 𝑖𝑓 𝑚 𝑎𝑛𝑑 𝑛 𝑎𝑟𝑒 𝑒𝑣𝑒𝑛
Proof. It is clear that ̅̅̅̅̅̅
𝐾𝑚,𝑛 ≡ 𝐾𝑚 ∪ 𝐾𝑛 , then, by using Observation 2.7(2), the result is obtained.

4. Conclusion
Through, this paper, a new domination parameter in the graphs it is called co-even domination
number is introduced. Many of the results of this number are obtained especially to certain graphs
as a path, cycle, star, wheel, complete, and complete bipartite.
References
[1] M. A. Abdlhusein and M. N. Al-Harere, Pitchfork Domination in Graphs, accepted in Discrete
Mathematics, Algorithms and Applications, (2019).
[2] M. A. Abdlhusein and M. N. Al-Harere, Doubly connected pitchfork domination and its inverse
in graphs, TWMS J. App. Eng. Math., (accepted to appear) (2020).
[3] M.N. Al-Harere, A. A. Omran, Binary operation graphs, AIP conference proceed-ing vol.2086,
Maltepe University, Istanbul, Turkey,030008, 31 July - 6 August (2018).
[4] J.A. Bondy and U.S.R. Murty, " Graph theory with applications". New york(1976).

333
ISSN: 2005-4297 IJCA
Copyright ⓒ 2020 SERSC
 International Journal of Control and Automation
Vol. 13, No. 3, (2020), pp. 330-334

[5] D. Z. Du and P. J . Wan , "Connected Dominating Set: Theory and Applications", Springer,
New York, 77, 2013.
[6] F. Harary, Graph Theory, Addison-Wessley, Reading Mass. (1969).
[7] T. W. Haynes, S. T. Hedetniemi and P.J. Slater, Fundamentals of domination in graphs, Marcel
Dekker, Inc., New York (1998).
[8] A. [Link], A. [Link], Domination in Discrete Topology Graph, Third International
Conference of Science(ICMS2019),Vol.2183(2019).
[9] N.J. Rad, Results on Total Restrained Domination in Graphs, Int .J. contemp. Math. Sciences,
Vol. 3, 2008, no.8, 383-387.
[10] A. A. Omran and Haneen H. Oda, "Hn-Domination in Graphs." Baghdad Science Journal
16.1 , 242-247,(2019)

334
ISSN: 2005-4297 IJCA
Copyright ⓒ 2020 SERSC
View publication stats