The rainbow connection number of enhanced power graph
Luis A. Dupont Daniel G. Mendoza Miriam Rodríguez




3mm
=-1cm
=-1.5cm



The rainbow connection number of enhanced power graph




[2]This work was partially supported by CONACYT.






Luis A. Dupont, Daniel G. Mendoza and Miriam Rodríguez.


Facultad de Matemáticas, Universidad Veracruzana


Circuito Gonzalo Aguirre Beltrán S/N;


Zona Universitaria;


Xalapa, Ver., México, CP 91090.


e-mail: ldupont@uv.mx







Let G be a finite group, the enhanced power graph of G, denoted by Γ_G^e, is the graph with vertex set G and two vertices x,y are edge connected in Γ_G^e if there exist z∈ G such that x,y∈⟨ z⟩. Let ζ be a edge-coloring of Γ_G^e. In this article, we calculate the rainbow connection number of the  enhanced power graph Γ_G^e.


  
Keywords: enhanced power graph; power graph; rainbow path; rainbow connection number.

AMS Mathematics Subject Classification: 05C25, 05C38, 05C45.





§ INTRODUCTION

Let G be a finite group, the power graph of a finite group G we denote the power graph by Γ_G, it is the graph whose vertex set are the elements of G and two elements being adjacent if one is a power of the other. In <cit.> the authors found that the power graph is contained in the non-commuting graph and, they asked about how much the graphs are closer, and then, they defined the enhanced power graph of a finite group. We denoted to the enhanced power graph by Γ_G^e whose vertex set is the group G and two distinct vertices x,y∈  V(Γ_G^e) are adjacent if x,y∈z for some z∈ G. Later, the enhanced power graph of a group was studied by Sudip Bera and A. K. Bhuniya <cit.>.


In 2006, Chartrand, Johns, McKean and Zhang <cit.> introduced the concept of rainbow connection of graphs. This concept was motivated by communication of information between agencies of USA government after the September 11, 2001 terrorist attacks. The situation that helps to unravel this issue about communications has as graph-theoretic model the following. Let Γ be a connected graph with vertex set V(Γ) and edge set E(Γ). We define a coloring ζE(Γ){1,...,k} with k∈ℕ. A path P is a rainbow if any two edges of P are colored distinct. If for each pair of vertices u,v∈ V(Γ), Γ has a rainbow path from u to v, then Γ is  rainbow-connected under the coloring ζ, and ζ is called a rainbow k-coloring of Γ. The rainbow connection number of Γ, denoted by rc(Γ) is the minimum k for which there exists a rainbow k-coloring of Γ.



We will apply the idea of calculating the rainbow connected number of enhanced power graph through the graphs such that as was carried out by the authors from  <cit.> about the power graph, with InvMax_G, the set of maximal involution of G, whose important theorems we can summarize in the following:


Let |InvMax_G|≠∅ and G be a finite group of order at least 3. Then


  rc(Γ_G)=

3,    if  1≤ |InvMax_G|≤ 2; 

|InvMax_G|,    if  |InvMax_G|≥ 3.


If |InvMax_G|=∅, let G be a finite group

  
  * If G is cyclic, then
rc(Γ_G) =

1,    if |G| is a prime power; 

2,    otherwise
  
  * If G es noncyclic, then rc(Γ_G)= 2 or 3.



In this paper we compute the rainbow connection number of Γ_G^e and we characterize it in terms of independence cyclic set, whose particular case is maximal involution. This paper is organized as follows. In section 2 we put definitions and some properties about rainbow connection number and we describe a way for guarantee a coloring for enchanced power graphs. In section 3 we wrote the main theorems for determine Γ_G^e.
















§ DEFINITIONS AND PROPERTIES

We start the section with a proposition from enhanced power graph definition.

  rc(Γ_G^e)=1 if only if Γ_G^e is complete if only if G is cyclic.



Let Max_G={x_1,...,x_m} be an essential cyclic set if

  
  * for all g∈ G, g=x_i for some i,
  
  * x_i≠x_j for i≠ j,
  
  * each x_i is a maximal cyclic subgroup.



Therefore <ref> can be rewritten as follows

|Max_G|=1 if only if  G is a cyclic group if only if rc(Γ_G^e)=1




  If |Max_G|=2, then rc(Γ_G^e)=2


  Since Γ_G^e is not complete, we have rc(Γ_G^e)≥ 2, then we have
  

  [             E_1               = {{a,b}|a,b∈x_1};             E_2               = {{a,b}|a,b∈x_2} ]
  

  We can note that the only one path  between x_1_j and  x_2_i for all x_1_j∈x_1 and x_2_i∈x_2 is (x_1_j,e,x_2_i), then the 2-coloring is given by ζ: E(G)⟶{1,2} with f↦ i, if f∈ E_i is a rainbow 2-coloring of Γ_G^e.




  We define the independence cyclic set of Max_G, denoted by ics(G), as
  
    ics(G)={x_i∈ Max_G|x_i∩x_j=e   for  i≠ j}

  The  independence cyclic number of Max_G, denoted by icn(G), is icn(G)=|ics(G)|.



We note that 
    InMax_G⊆ ics(G)⊆ Max_G.




  If |Max_G|=3, then 
    rc(Γ_G^e)=
                                       2,     icn(G)=1 
    
                                       3,     icn(G)=3



  Let Max_G={x_1,x_2,x_3} be an essential cyclic set.


 We do not need to be concise with the path with both vertex in x_i for some i, because with one color, we can coloring this path. The difficult is when both vertex are in different x_i.



Case cin(G)=1 Without loss of generality we suppose x_1∩x_2=e=x_1∩x_3 and x_2∩x_3≠ e. Since G is not cyclic group, then rc(Γ_G^e)≥ 2. Let h∈x_2∩x_3 with h≠ e, thus
      

[                                                    E_1                                                      =        {{a,b}|{a,b}⊂x_1}⋃{{a,b}|{a,b}⊂x_2 with a,b≠ e};                                                    E_2                                                      = {{e,g}|g∈x_2∪x_3}⋃{{a,b}|a∈x_3∖x_2,   b∈x_2∩x_3, b≠ e} ]
  

  In particular {h,g}∈ E_2 for all g∈x_3∖x_2. Then, we will give a 2-coloring to Γ_G^e:
  
    [ ζ:E(G)      ⟶  {1,2};      f      ↦      i ] if  i∈ E_i




Case cin(G)=3 We suppose that |InMax_G|=0, and without loss of generality x_i∩x_j=e for 1≤ i<j≤ 3. We will give a 3-coloring for Γ_G^e, with

    [                                 E_1                                   =                {{x_i,e}|i=1,2,3   };                                 E_2                                   = {{e,x_i_j}|x_i_j∈⋃_i=1^3x_i∖ x_i  };                                 E_3                                   =       {{a,b}|a,b∈x_i for i=1,2,3  } ]


 With the coloring
   
    [  ζ:E(G)       ⟶ {1,2,3};       f       ↦       i ]if  i∈ E_i



Now, we suppose that InMax_G=Max_G, then with E_i={{a,b}|a,b∈x_i} be the edges set, and the coloring is given like <ref>.


We can not give a 2-coloring for Γ_G^e. We claim that there is a 2-coloring. Let u∈x_1, v∈x_2 and w∈x_3. Then, we have ζ(u,e)=1 and ζ(e,v)=2, thus (u,e,v) is a desire rainbow path. Likewise ζ(u,e)=1 and ζ(e,w)=2, but for (v,e,w) there is not a rainbow path.




From <ref> we can ask ourself about what happens whether no one of x_i can be intersected by another x_j with i≠ j or, what happens if all x_i are intersected with some common elements. For this, we have the following prepositions.


The following preposition is just like <cit.>


  Let Max_G={x_1,...,x_m} be an essential cyclic set and InMax_G=Max_G. Then rc(Γ_G^e)=m.


For Γ_G^e we will give a m-coloring. For each i=1,...,m we have

    E_i(G)={{a,b}|a,b∈x_i}

since for u∈x_i and v∈x_j with i≠ j we have a only one path between them, which is (u,e,v), and the coloring is given by

    [       ζ: E(G)             ⟶     {1,...,m};             f             ↦ i  if  f∈ E_i ]

We can see the diagram in figure <ref>.





Let Max_G={x_1,...,x_m} be an essential cyclic set with m≥ 2, and h_i,j∈x_i∩x_j for 1≤ i<j≤ m. If h_i,j≠ h_r,s, with i≠ r or j≠ s, then rc(Γ_G^e)=2.


By <ref> we only give the coloring for x_i and x_j such that i< j. We fix


E_1(G)={{a,h_i,j}|a∈x_i∖x_j}⋃{{a,b}|a,b∈x_i}

E_2(G)={{b,h_i,j}|b∈x_j∖x_i}⋃{{a,b}|a,b∈x_j}




Then, we always have a path for x_i_r∈x_i to x_j_s∈x_j given by (x_i_r,h_i,j,x_j_s) with i<j,  and the coloring is the same given in <ref>.



The next definition guarantees the existence of a coloring for Γ_G^e.


  An awning is a collection H_1,...,H_m-1 where the following occurs:
  
    
  * H_i=A_i⋃̇ B_i={h_i,i+1,...,h_i,m}⊂X_i for i=1,...,m-1
    
  * for all i<j, h_i,j∈x_i∩x_j
    
  * for i<j with j=2,...,m-1 , if h_j,s=h_i,r∈ H_j∩ H_i (s∈{j+1,...,m}, and r∈{i+1,...,m}), the following holds:
    
      
  * r=j, h_i,r∈ A_i, then h_j,s∈ B_j
      
  * r=j, h_i,r∈ B_i, then h_j,s∈ A_j
      
  * r=s>j, h_i,r∈ A_i, then h_j,r∈ A_j
      
  * r=s>j, h_i,r∈ B_i, then h_j,r∈ B_j
    
  



The case in  <ref> is a particular case where G has not an awning. By definition of awning we want to say, if we have an awning, then we only need H_i={e} for only some i, and no more.





If G has an awning and |Max_G|≥ 3, then icn(G)≤ 1. In particular, |InMax_G|≤ 1.


Suppose that icn(G)=2, then H_i_1=H_i_2={e}. Hence (x_i_1,e,x_i_2) is a rainbow path, and (x_i_1,e,x_i_3) is another rainbow path, but in (x_i_2,e,x_i_j) we have not a rainbow path for Γ_G^e.



  If |∩ H_i|≥ m-1 with Max_G=m, then G has an awning.



If |Max_G|=2 then icn(G)=0 or 2, and G has an awning.



  If G has an awning, then icn(G)=1. In particular |InMax_G|≤ 1.



  We note that the coloring whether we have to InMax_G or ics(G) does not change, both can be colored by only one color. The only one difference due to in InMax_G there is only two elements in the subset of G and, for a set taken of  ics(G) there are more than two elements but, the behaviour in coloring is exactly the same, because, in a set taken of ics(G) all the elements are associated each them, then, one color is enough for coloring all set.


In the following properties we only consider the set ics(G) unless otherwise indicated.

  If G has an awning, then rc(Γ_G^e)=2


  We will give to Γ_G^e a rainbow 2-coloring, for 1≤ r < s ≤ m, let:

    

 [                           E_r,s^1                                 = {{a,h_r,s}|a∈x_r\x_s; h_r,s∈ A_r};                           E_r,s^2                                 = {{b,h_r,s}|b∈x_s\x_r; h_r,s∈ A_r};                           E_r,s^1                                 = {{a,h_r,s}|a∈x_r\x_s; h_r,s∈ B_r};                           E_r,s^2                                 = {{b,h_r,s}|b∈x_s\x_r; h_r,s∈ B_r} ]

 

  Write E_1=⋃_1≤ r < s ≤ m E_r,s^1 and E_2=⋃_1≤ r < s ≤ m E_r,s^2 and we define a coloring

    

 [     ζ: E(Γ_G^e)               ⟶           {1,2};               f               ↦ i,   if  f∈ E_i ]
  

We go to check that, this is a 2-coloring for Γ_G^e. We will make a coloring for j,s-step. If this edges have been colored in a before step, i.e., if h_j,s=h_i,r with i<j, thus we will have coloring problems with r=j or r=s.


For r=j (r=s), for (a)-(d) from <ref> we can guarantee in before step we can conserve the coloring and that, not affect us with the 2-coloring that we gave.



If rc(Γ_G^e)=2, then for any order of Max_G, we have an awning.


We have rc(Γ_G^e)=2  and suppose E_1⋃̇E_2=E be the set of edges of Γ_G^e and a 2-coloring give by <ref> and let Max_G={x_1,...,x_m} be an independence cyclic set of Γ_G^e, thus there is h∈x_i∩x_j such that {x_i,h}∈ E_1 and {h,x_j}∈ E_2 (or {x_i,h}∈ E_2 and {h,x_j}∈ E_1). We define h_i,j:=h, moreover H_i:={h_i,1,...,h_i,m}=:A_i⋃̇B_i such that


  A_i={h_i,j|{x_i,h_i,j}∈ E_1} and B_i={h_i,j|{x_i,h_i,j}∈ E_2},


where (a)-(b) from <ref> are met.



If G has an awning with any order on Max_G, then for every order, G has an awning.




rc(Γ_G^e)=2 if only if G has an awning and G is not cyclic group.


By <ref> and <ref>


By <ref> we obtain a similar proposition like <cit.>.


Let Max_G={x_1,...,x_m} be an essential cyclic set. If InMax_G≠∅, then |InMax_G|≤ rc(Γ_G^e).


As in the proof of <cit.>.



Let Max_G={x_1,...,x_m} be an essential cyclic set. If icn(G)≥ 3, then 3≤ rc(Γ_G^e).




  Suppose that |InMax|=0 and ics(G)={x_1,...,x_k} be an independence cyclic set with k≥ 3. We can not give a 2-coloring for the graph induced by x_1∪⋯∪x_k, but we will give a 3-coloring induced by the following edge sets
  
    [                                 E_1                                   =              {{x_i,e}|i=1,...,m   };                                 E_2                                   = {{e,x_i_j}|x_i_j∈⋃_i=1^mx_i∖ x_i  };                                 E_3                                   =        {{a,b}|a,b∈x_i for each i  } ]



  with the rest edges just like <ref> and <ref>. Thus the 3-coloring is given by <ref>.


  If |InMax_G|≥ 3 then the edges set is
  
    [                                   E_1                                     =              {{x_i,e}|i=l+1,...,m   };                                   E_2                                     = {{e,x_i_j}|x_i_j∈⋃_i=l+1^mx_i∖ x_i  };                                   E_3                                     =          {{a,b}|a,b∈x_i for each i  };                                   E_i                                     =                  {{x_i,e}|i=1,...,l } ]

and the coloring given by
  
    [    ζ:E(G)         ⟶ {1,...,l};         f         ↦         i ] if f∈ E_i

 






In particular we have the following


  Let Max_G={x_1,...,x_m} be a essential cyclic group with m≥ 4 and icn(G)≥ 2, then 3≤ rc(Γ_G^e).






We have rc(Γ_G^e)≤ rc(Γ_G) because E(Γ_G)⊆ E(Γ_G^e).




§ MAIN THEOREMS

In this section we prove our main theorems.


  Let Max_G={x_1,...,x_m} be an essential cyclic set. If icn(G)=1 then rc(Γ_G^e)=1 if only if m=1. In particular, if |InMax_G|=1 then rc(Γ_G^e)=1 if only if G≅ℤ_2.


  By <ref>, <ref> and <ref>.



  Let Max_G={x_1,...,x_m} be an essential cyclic set. If icn(G)=1 then rc(Γ_G^e)=2 if only if G has an awning.


  By <ref>, <ref> and <ref>.



  Let Max_G={x_1,...,x_m} be a essential cyclic set with m≥ 3. If icn(G)=1 then rc(Γ_G^e)=3 if only if G has not an awning.


By <ref>.


Let Max_G={x_1,...,x_m} be a essential cyclic set with m≥ 4. If icn(G)=2, then rc(Γ_G^e)=3.


 By <ref> and <ref>.



  Let Max_G={x_1,...,x_m} be an essential cyclic set. If icn(G)≥ 3, then rc(Γ_G^e)=|InMax_G|.


  By <ref> and <ref>.



 Let Max_G={x_1,...,x_m} be an essential cyclic set with icn(G)=0, then
rc(Γ_G^e)=

  1,    

  2,    

  3,    .


  Case 1 By <ref>.

  Case 2 By <ref>.

  Case 3 By <ref>, <ref>.




















10


Aalipour G. Aalipour, S. Akbari, P. J. Cameron, R. Nikandish and F. Shaveisi. On the structure of the power graph and
the enhanced power graph of a group. The Electronic Journal of Combinatorics, 24(3), #P3.16, 2017.

Abe S. Abe and N. Iiyori. A generalization of prime graphs of finite groups.Hokkaido Math.
J., 29(2):391–-407, 2000.

AndersonLivings D. F. Anderson, P. S, Livingston. The zero-divisor graph of a commutative ring.
J. Algebra. 217:434–447, 1999.


Atani S. E. Atani.A ideal based zero divisor graph of a commutative semiring.Glasnik Matematicki. 44(64):141–153, 2009.







Bera-Bhuniya S. Bera, A. K. Bhuniya. On some properties of enhanced power graph.  arXiv:1606.03209v1, 2016.

Bera-Bhuniya2 S. Bera, A. K. Bhuniya. Normal subgroup based power graph of a finite Group.  Communications in Algebra, 45 (8): 3251–3259, 2017.

Chakrabarty I. Chakrabarty, S. Ghosh, M. K. Sen. Undirected power graphs of semigroups. Semigroup Forum. 78:410–426, 2009.

Chartrand G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang. Rainbow connection in graphs. Math. Bohem. 133 85-98, 2008.

Diestel R. Diestel. Graph theory. volume 173 of Graduate Texts in Mathematics. Springer-Verlag,
Berlin, third edition, 2005.














 

Ma X. Ma, M. Feng, and  K. Wang. The Rainbow Connection Number of the Power Graph of a Finite Group. Graphs and Combinatorics. 32: 1495, 2016

Redmond S. P. Redmond.An ideal-based zero divisor graph of a commutative ring. Communication
in algebra. 31:4425–4443, 2003.

Willians J. S. Williams.Prime graph components of finite groups. J. Algebra, 69:487–-513, 1981.






