Ratio Mathematica                                                                         Volume 44, 2022 

 
 

                                                                                                                                    

 

 

 

           

Co-even Geodetic Number of a Graph 

 
 

T. Jebaraj * 

Ayarlin Kirupa.M † 

 
 

 

Abstract 

Let 𝐺 = (𝑉, 𝐸)  be  a graph with vertex set 𝑉 and edge set 𝐸. If 𝑆 is a set of vertices of 
𝐺, then 𝐼[𝑆] is the union of all sets 𝐼[𝑢, 𝑣] for 𝑢, 𝑣 ∈ 𝑆. If 𝐼[𝑆] = 𝑉(𝐺), then 𝑆 is a 
geodetic set for 𝐺. The geodetic number 𝑔(𝐺) is the minimum cardinality of a geodetic 
set. A geodetic set 𝑆 is called co- even geodetic set if the degree of vertex 𝑣 is even 
number for all 𝑣 ∈ 𝑉 − 𝑆. The cardinality of a smallest co- even geodetic set of 𝐺, 
denoted by 𝑔𝑐𝑜𝑒(𝐺) is the co- even geodetic number of 𝐺. In this paper, we find the co- 
even geodetic number of certain graphs and complement graphs. 

 

Keywords: geodetic set, co-even geodetic set, co-even geodetic number 

 

2010 AMS subject classification: 05C12.‡ 

 

 

 

 

 

 

 

 
 

*Assistant professor, Research Department of Mathematics, Malankara Catholic College, Mariagiri, 

Kaliakkavilai, India; jebaraj.math@gmail.com 

†Research Scholar, Reg. No.20113082092003, Research Department of Mathematics, Malankara Catholic 

College, Mariagiri, Kaliakkavilai, India; ayarlin.kirupa19@gmail.com. 
‡Affiliated to Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli-627012, Tamilnadu, 

India; Received on June 6 th, 2022. Accepted on Sep 1st, 2022. Published on Nov 30th, 2022. doi: 

10.23755/rm.v44i0.922. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors.This paper is published 

under the CC-BY licence agreement. 

 

332



 

 

T. Jebaraj, Ayarlin Kirupa.M 

 

 

 

1. Introduction 

By a graph 𝐺 = (𝑉, 𝐸), we mean a finite undirected connected graph without loops 
or multiple edges. As usual 𝑛 =  |𝑉| and 𝑚 =  |𝐸| denote the number of vertices and 
edges of a graph 𝐺 respectively. The minimum and maximum degree 𝛿(𝐺) and Δ(𝐺), 
respectively. In case where Δ(𝐺) = 𝛿(𝐺), 𝐺 is called a regular graph. The distance 
𝑑(𝑥, 𝑦) is the length of a shortest 𝑥 − 𝑦 path in 𝐺. It is known that the distance is a 
metric on the vertex set of G. An 𝑥 − 𝑦 path of length 𝑑(𝑥, 𝑦) is called an 𝑥 − 𝑦 
geodesic. For any vertex  𝑢 of 𝐺,the eccentricity of 𝑢 is 𝑒(𝑢) =  𝑚𝑎𝑥{𝑑(𝑢, 𝑣) ∶  𝑣 ∈
 𝑉}.    A vertex 𝑣 is an eccentric vertex of 𝑢 if 𝑒(𝑢) =  𝑑(𝑢, 𝑣). The neighborhood of a 
vertex 𝑣 is the set 𝑁(𝑣) consisting of all vertices 𝑢 which are adjacent with 𝑣. A vertex 
𝑣 is an extreme vertex of 𝐺 if the subgraph induced by its neighbors is complete. The 
closed interval 𝐼[𝑥, 𝑦] consists of all vertices lying on some 𝑥 − 𝑦 geodesic of 𝐺, while 
for 𝑆 ⊆ 𝑉  ,             [𝑆] =   ⋃ 𝐼[𝑥, 𝑦]𝑥,𝑦∈𝑆  . A set S of vertices is a geodetic set if 𝐼[𝑆] =

𝑉 and the minimum cardinality of a geodetic set is the geodetic number 𝑔(𝐺). In this 
paper, we study the co-even geodetic number and is denoted by 𝑔𝑐𝑜𝑒(𝐺) also we discuss 
the co-even geodetic number of some standard graphs.  

 

 

2. Co-even geodetic number of a graph 

Definition 2.1 A geodetic set 𝑺 is called co-even geodetic set if the degree of vertex 
𝒗 is even number for all 𝒗 ∈ 𝑽 − 𝑺. The cardinality of a smallest co-even geodetic 
set of 𝑮, denoted by 𝒈𝒄𝒐𝒆(𝑮) is the co-even geodetic number of 𝑮.  
 

Example 2.2 

                                       
Figure 2.1 

 

     In figure 2.1, 𝑆 = {𝑣1, 𝑣3, 𝑣4, 𝑣5}  is a co-even geodetic set. Here, the vertices 𝑣1 and 
𝑣4 has odd degree. These two vertices do not make a geodetic set and no 3- element 
subset of 𝐺 is a co-even geodetic set. Then it is clear that 𝑔𝑐𝑜𝑒 (𝐺) = 4. 

 

333



                      Co-even geodetic Number of a graph 

Remark In figure 2.1, 𝑆 = {𝑣1, 𝑣3, 𝑣5} is the minimum geodetic set of 𝐺. ie) 𝑔(𝐺) = 3. 
Thus, the geodetic number and co-even geodetic number of a graph 𝐺 can be different. 
 

Proposition 2.3 Let 𝐺 be a graph and 𝑆 is a co-even geodetic set . Then, 
i)  All vertices of odd degrees belong to every co-even geodetic set. 

ii) 𝑑𝑒𝑔(𝑣) ≥ 2 for all  𝑣 ∈ 𝑉 − 𝑆. 
 

Proposition 2.4 If 𝐺 is 𝑝- regular graph, then 𝑔𝑐𝑜𝑒 (𝐺) = {
𝑛   𝑖𝑓   𝑝  𝑖𝑠 𝑜𝑑𝑑

𝑔(𝐺) 𝑖𝑓  𝑝  𝑖𝑠  𝑒𝑣𝑒𝑛
 

 

Theorem 2.5 If  𝐺 be a graph of order 𝑛, then 2 ≤ 𝑔(𝐺) ≤ 𝑔𝑐𝑜𝑒 (𝐺) ≤ 𝑛. 
Proof: A geodetic set needs atleast two vertices. Therefore, 𝑔(𝐺) ≥ 2. Clearly, every 
co-even geodetic set is a geodetic set of 𝐺, 𝑔(𝐺) ≤ 𝑔𝑐𝑜𝑒(𝐺) . Also, all the vertices of 𝐺 
is the co-even geodetic set of 𝐺.ie) 𝑔𝑐𝑜𝑒 (𝐺) ≤ 𝑛. 
 

Remark 2.6 The bounds of the theorem 2.5 are sharp. The co-even geodetic number of 

paths 𝑃𝑛 with 𝑛 vertices is 2. In this case, the smallest bounds is obtained. Also, 𝐾𝑛 with 
𝑛 vertices have the co-even geodetic number is 𝑛. Then the upper bound is obtained. 
 

Theorem 2.7 If 𝐺 is a non trivial connected graph with 𝑛 ≥ 2.If 𝑔𝑐𝑜𝑒 (𝐺) = 2 then 
𝑔(𝐺) = 2. 
Proof. It is follows from theorem 2.5. 

 

Remark 2.8 The converse part of above theorem is need not be true for all graphs. In 

Figure 2.2, The minimum geodetic number is 2 and the minimum co-even geodetic 

number is 3. 

                                   
                                                    Figure 2.2 

 

Corollary 2.9 Let 𝐺 be the non-trivial connected graph, 𝑔(𝐺) = 2 then 𝑔𝑐𝑜𝑒 (𝐺) = 2. 
Proof. Case (i) If 𝐺 = 𝐾2 
     It is easy to see 𝑔(𝐾2) = 2 then 𝑔𝑐𝑜𝑒(𝐾2) = 2. 
Case (ii) All the vertices of 𝐺 should be even degree. 
     Consider the even Cycle 𝐶2𝑛. All vertices have even degree for 𝐶2𝑛.We know that 
𝑔(𝐶2𝑛) = 2. Further more, 𝑔𝑐𝑜𝑒 (𝐶2𝑛) = 2. 

334



 

 

T. Jebaraj, Ayarlin Kirupa.M 

 

 

 

Case (iii) A graph with exactly two odd degree vertices which only belongs to the 

minimum geodetic set. 

 

                                  
     For example, In Figure 2.3, the vertices  𝑣3 and 𝑣5  have odd degree and 𝑣1, 𝑣2, 𝑣4 
have even degree. The minimum geodetic number of 𝐺 is 2. Also, it is easily seen that 
𝑔𝑐𝑜𝑒 (𝐺) = 2. 
 

Remark All the graphs are not satisfied for the corollary 2.9 except the above three type 

graphs. 

Observation. 2.10 𝑔𝑐𝑜𝑒(𝐶𝑛) = 𝑔(𝐶𝑛 ),  where 𝐶𝑛 is a cycle of order 𝑛. 
Proof. Every cycle is the 2- regular graph .by the proposition 2.4, we get         

𝑔𝑐𝑜𝑒 (𝐶𝑛) =  𝑔(𝐶𝑛). 
 

Theorem 2.11 For the Wheel graph 𝑊𝑛  (𝑛 ≥ 4), then 

                                         𝑔𝑐𝑜𝑒 (𝑊𝑛) = {
𝑛 − 1   𝑖𝑓  𝑛  𝑖𝑠   𝑜𝑑𝑑
𝑛   𝑖𝑓   𝑛    𝑖𝑠   𝑒𝑣𝑒𝑛 

 

 

Proof. Case (i)  𝑛  is  odd 
     Let  𝑊𝑛  =  𝐾1 +  𝐶𝑛−1  and  𝑢  be the vertex of 𝐾1. It is easy to see that the 𝑛 − 1 
vertices has odd degree except the vertex 𝑢. By the proposition 2.3, 𝑛 − 1 vertices 
belong to the co-even geodetic set 𝑆. Also, the vertex 𝑢 ∈ 𝑉 − 𝑆, which has even 
degree. Hence |𝑆| = 𝑛 − 1. 
Case (ii)  𝑛 is even. 
     Every vertex of 𝑊𝑛  has  odd degree. By the proposition 2.3,  All the vertices  of 𝑊𝑛  
belongs  to the co-even  geodetic set. Therefore,  𝑔𝑐𝑜𝑒 (𝑊𝑛) = 𝑛. 

 

Corollary 2.12 For the wheel graph with 𝑛 ≥ 4 then 𝑔𝑐𝑜𝑒 (𝑊𝑛)= 2𝛼0(𝑊𝑛) − 2. 

Proof. We prove this theorem by two cases. 

335



                      Co-even geodetic Number of a graph 

Case (i) 𝑛 is even 

     We have 𝑔𝑐𝑜𝑒(𝑊𝑛) = 𝑛  if  𝑛  is even and 𝛼0(𝑊𝑛) =
𝑛+2

2
. 

We have 𝑔𝑐𝑜𝑒 (𝑊𝑛) = 𝑛  .                                                                                                                                                   

𝑔𝑐𝑜𝑒 (𝑊𝑛) + 2 = 𝑛 + 2. Then 
𝑔𝑐𝑜𝑒(𝑊𝑛)+2

2
=

n+2

2
 

𝑔𝑐𝑜𝑒 (𝑊𝑛)

2
+ 1 = 𝛼0(𝑊𝑛) 

𝑔𝑐𝑜𝑒(𝑊𝑛) = 2𝛼0(𝑊𝑛) − 2 
Case (ii) 𝑛 is odd 

Since 𝑔𝑐𝑜𝑒 (𝑊𝑛) = 𝑛 − 1 if n is odd and 𝛼0(𝑊𝑛) =
𝑛+1

2
 

We have 𝑔𝑐𝑜𝑒 (𝑊𝑛)  =  𝑛 − 1 
 

𝑔𝑐𝑜𝑒 (𝑊𝑛) + 1

2
=

n − 1 + 1

2
 

𝑔𝑐𝑜𝑒 (𝑊𝑛) 

2
=

𝑛 + 1

2
− 1 

𝑔𝑐𝑜𝑒 (𝑊𝑛)  =  2𝛼0(𝑊𝑛) − 2. 
 

Theorem 2.13 If 𝐺 is the double fan graph 𝐹 =  𝑃𝑛 + 𝐾2̅̅ ̅ with 𝑛 ≥ 5,  then 𝑔𝑐𝑜𝑒 (𝐺) =
4. 
Proof 

 
                                      Figure 2.4 

 

     Let  𝑝1, 𝑝2,…, 𝑝𝑛  be the vertices of path 𝑃𝑛 and let  𝑥 and 𝑦 be the two vertices of 
𝐾2̅̅ ̅. All the vertices of path 𝑃𝑛 is adjacent to 𝑥 and 𝑦. Now, the double fan graph 𝐹 =
 𝑃𝑛 + 𝐾2̅̅ ̅ have the 𝑛 + 2 vertices. We prove this theorem by two cases. 
Case (i) 𝑛 is odd 
     If 𝑛 is odd then the end vertices of 𝑃𝑛   and the vertices of 𝐾2̅̅ ̅   have the odd degree. 
By the proposition 2.3, these four vertices 𝑝1, 𝑝𝑛 ,𝑥,𝑦  belongs to co-even geodetic set. 
Also all the vertices of 𝐹 lies on any geodesic of the co-even geodetic set. Thus 
𝑔𝑐𝑜𝑒 (𝑃𝑛 + 𝐾2̅̅ ̅) = 4. 

336



 

 

T. Jebaraj, Ayarlin Kirupa.M 

 

 

 

Case (ii)  𝑛 is even 
     If 𝑛  is even then all the vertices of 𝐹 is even degree except the vertices 𝑝1 and 𝑝𝑛  
belongs to co-even geodetic set. All the vertices of 𝐹 does not lies the 𝑝1 − 𝑝𝑛 geodesic. 
So we chosen the vertices 𝑥 and 𝑦  in the co-even geodetic set. Now the set               𝑆 =
{𝑝1, 𝑝𝑛 , 𝑥 , 𝑦}  is the co-even geodetic set as well as all the vertices of 𝑉 − 𝑆 has even 
degree. Therefore,  𝑔𝑐𝑜𝑒(𝑃𝑛 + 𝐾2̅̅ ̅) = 4. 
 

Corollary 2.14 For the double fan graph 𝐹 =  𝑃𝑛 + 𝐾2̅̅ ̅ with 𝑛 ≥ 5 then, 

   𝑔𝑐𝑜𝑒 (𝑃𝑛 + 𝐾2̅̅ ̅) = {
2𝛼0(𝑃𝑛 + 𝐾2̅̅ ̅)  − 𝑛 + 1    𝑖𝑓  𝑛  𝑖𝑠  𝑜𝑑𝑑

2𝛼0(𝑃𝑛 + 𝐾2̅̅ ̅)  − 𝑛         𝑖𝑓  𝑛  𝑖𝑠  𝑒𝑣𝑒𝑛 
 

Theorem 2.15 For the ladder graph 𝐿𝑛 then, 𝑔𝑐𝑜𝑒 (𝐿𝑛) = 2𝑛 − 2. 

Proof 

                           
                                                        Figure 2.5 

     The ladder graph 𝐿𝑛with 2𝑛 vertices. The geodetic number of 𝐿𝑛 is 2.           𝑆 =
{𝑣1, 𝑣2𝑛 }  or {𝑣𝑛, 𝑣𝑛+1}  is the minimum geodetic set of 𝐿𝑛, which is not a co-even 
geodetic set. Because some vertices of  𝑉 − 𝑆  has odd degree. Therefore, the odd 
degree vertices {𝑣2, 𝑣3,…, 𝑣𝑛−1, 𝑣𝑛+2,…, 𝑣2𝑛+1} is belong to the co-even geodetic set 
of 𝐿𝑛. Therefore, all the vertices of 𝐿𝑛 except two vertices make the co-even geodetic 
set. Hence  𝑔𝑐𝑜𝑒 (𝐿𝑛)  = 2𝑛 − 2. 

 

Theorem2.16 For the Cone graph 𝐶𝑚 + �̅�𝑛 then 𝑔𝑐𝑜𝑒(𝐶𝑚 +

�̅�𝑛) = {

𝑛  𝑖𝑓  𝑛  𝑖𝑠  𝑒𝑣𝑒𝑛,              𝑚 ≥ 5
𝑚  𝑖𝑓  𝑚  𝑖𝑠  𝑒𝑣𝑒𝑛 ,    𝑛  𝑖𝑠  𝑜𝑑𝑑

𝑚 + 𝑛  𝑖𝑓  𝑚  𝑖𝑠  𝑜𝑑𝑑,   𝑛  𝑖𝑠  𝑜𝑑𝑑
 

Proof. The Cone graph 𝐶𝑚 + �̅�𝑛  is  adding with cyclic graph 𝐶𝑚 and empty graph �̅�𝑛. 
The cone graph has 𝑚 + 𝑛 vertices. We prove this theorem by three cases. 
Case (i) If 𝑛 is even 
     In this case, we prove with two subcases. 

Sub Case (i) If 𝑛 is even, 𝑚 is odd 
     For the Cone graph 𝐶𝑚 + �̅�𝑛  , only 𝑛 vertices have odd degree. By the proposition 
2.3, 𝑛- vertices belongs to the co-even geodetic set. Now, every vertex belongs to any 
geodesic of the co-even geodetic set. Hence 𝑔𝑐𝑜𝑒 (𝐶𝑚 + �̅�𝑛) = 𝑛. 
Sub Case (ii) If 𝑛 is even, 𝑚 is even 

337



                      Co-even geodetic Number of a graph 

     Both the vertices of 𝐶𝑚 + �̅�𝑛  has even degree. Now, 𝑛- vertices forms a                
co-even geodetic set of  𝐶𝑚 + �̅�𝑛. Hence 𝑔𝑐𝑜𝑒(𝐶𝑚 + �̅�𝑛) = 𝑛. 
Case (ii) If  𝑚  is even and 𝑛 is odd 
     Let 𝑚 is even number of vertices and 𝑛 is odd number of vertices. Here, 𝐶𝑚 + �̅�𝑛  
has  𝑚- even vertices have odd degree and  𝑛-odd vertices have even degree. Then it 
follows from the sub case (i) we get  𝑔𝑐𝑜𝑒(𝐶𝑚 + �̅�𝑛) = 𝑚. 
Case (iii) If both 𝑚 and 𝑛 are odd 
     For all the vertices of 𝐶𝑚 + �̅�𝑛 have odd degree. Then it follows from the subcase 
(i). Thus, we get, 𝑔𝑐𝑜𝑒 (𝐶𝑚 + �̅�𝑛) = 𝑚 + 𝑛. Hence proved. 
 

 

3.Co-even geodetic number of Complement of a graph 

Theorem 3.1 If 𝑃𝑛 is a path graph with 𝑛 ≥ 5 ,then 𝑔𝑐𝑜𝑒 (𝑃�̅�) = {
4       𝑖𝑓    𝑛   𝑖𝑠   𝑜𝑑𝑑

𝑛 − 2   𝑖𝑓   𝑛   𝑖𝑠  𝑒𝑣𝑒𝑛
 

Proof. Let 𝑢 and 𝑣 be the end vertices of 𝑃𝑛. The vertices 𝑢 and 𝑣 are adjacent to    𝑛 −
2 vertices in 𝑃�̅�. The remaining vertices are adjacent to 𝑛 − 3 vertices in 𝑃�̅�. 
Case (i) If 𝑛 is odd 
     Since 𝑢 and 𝑣  are adjacent to 𝑛 − 2 vertices in 𝑃�̅�. Clearly, 𝑢 and 𝑣 are odd vertices. 
Therefore {𝑢 , 𝑣} ∈ 𝑆. Also, {𝑢 , 𝑣} is not a geodetic set. Consider a vertex 𝑥, which is 
adjacent to 𝑣 and non adjacent to 𝑢. Obviously, 𝑛 − 3 vertices lie on the 𝑥 − 𝑢 
geodesic. Choose a vertex 𝑦 there exist 𝑦 ∈ 𝑉(𝑃�̅�) such that 𝑦 ∉ 𝐼[𝑥 , 𝑢]. Also no 3- 
element subset contains the      co-even geodetic set. Hence, 𝑆 = {𝑢 , 𝑣 , 𝑥 , 𝑦} is the 
minimum co-even geodetic set. 

Case (ii) If 𝑛 is even 
     For 𝑛 is even, clearly, 𝑢 and 𝑣 are even degree vertices. Remaining 𝑛 − 2 vertices 
are adjacent to 𝑛 − 3 vertices. Obviously, 𝑛 − 2 vertices is odd vertices. Also, every 
vertex lies on the any geodesic of  𝑛 − 2 vertices. Therefore, the minimum co-even 
geodetic number is 𝑛 − 2. ie) 𝑔𝑐𝑜𝑒 (𝑃�̅�) = 𝑛 − 2. 

 

Theorem 3.2 For any Gear graph 𝐺𝑛 with 𝑛 ≥ 3 then 𝑔𝑐𝑜𝑒 (𝐺𝑛̅̅ ̅) = 𝑛 + 1. 
Proof. For the Gear graph 𝐺𝑛 ,if 𝑛 is odd, then 𝐺𝑛̅̅ ̅ has 𝑛 + 1 odd vertices. By the 
proposition 2.3, 𝑛 + 1 vertices belong to co-even geodetic set. Moreover, if 𝑛 is even, 
then the graph 𝐺𝑛̅̅ ̅ has 𝑛 vertices have odd degree. These 𝑛 vertices containing the      
co-even geodetic set. It is easy to see that all vertices do not lies any geodesic of       co-

even geodetic set. So we add one more vertex in co-even geodetic set. Obviously, 

𝑔𝑐𝑜𝑒 (𝐺𝑛̅̅ ̅) = 𝑛 + 1. 

 

Theorem 3.3 For the complement of the cycle 𝐶𝑛̅̅ ̅ with 𝑛 ≥ 5, then 𝑔𝑐𝑜𝑒(𝐶𝑛̅̅ ̅) =

{
3   𝑖𝑓   𝑛   𝑖𝑠  𝑜𝑑𝑑

𝑛   𝑖𝑓   𝑛   𝑖𝑠   𝑒𝑣𝑒𝑛
 

Proof. This theorem follows from the Theorem 3.1 

338



 

 

T. Jebaraj, Ayarlin Kirupa.M 

 

 

 

4. Conclusions 

     In this paper, we obtained co-even geodetic number of some kind of graphs and 

complement of some graphs. Also, we see the relation between vertex covering and     

co-even geodetic number of some graphs. 

 

References 
 

[1] F. Buckley and F. Harary, Distance in graphs, Addison- Wesley, Reading, MA 

(1990) 

[2] G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, 

Networks, 39(2002), 1-6. 

[3] Manar M. Shalaan and Ahmed A. Omran, Co Even Domination In Graphs, 

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

[4] Manar M. Shalaan and Ahmed A. Omran, Co Even Domination in Some Graphs, 

IOP Conf. Series: Materials Science and Engineering 928 (2020) 042015. 

[5] Nima Ghanbari, More on co even domination number, arXiv:2111.11817v2 

[math.CO] 19   Jan 2022. 

 

339