On Oriented Diameter of Power Graphs
Deepu Benson Bireswar Das Dipan Dey Jinia Ghosh



Toward Realistic Solar Flare Models
    M. Haahr
          1,2
          B. V. Gudiksen1,2
          Å. Nordlund 1,3
          
    September 9, 2024
===========================================================================================



§ ABSTRACT 
In this paper, we study the oriented diameter of power graphs of groups. We show that a 2-edge connected power graph of a finite group has oriented diameter at most 4. We prove that the power graph of a cyclic group of order n has oriented diameter 2 for all n≠ 2,4,6. Until our work, to the best of our knowledge, no infinite family of graphs with oriented diameter 2 had been identified except for subclasses of complete graphs. Finally, we give a complete characterization of the oriented diameter of the power graphs of nilpotent groups. This, in turn, gives an algorithm for computing the oriented diameter of the power graph of a given nilpotent group that runs in time polynomial in the size of the group.









§  INTRODUCTION


An orientation   of an undirected graph X is an assignment of exactly one direction to each of the edges of X. An orientation is called a strong orientation if any two vertices are reachable from each other by directed paths introduced by the orientation. It is easy to see that a graph with a bridge cannot admit a strong orientation. In 1939, Robbins <cit.> proved that a graph is strongly orientable if and only if it is 2-edge connected[A graph is 2-edge connected if and only if it is bridgeless and connected.].   


The diameter of an undirected graph is the maximum distance between any two vertices in the graph. We denote the class of 2-edge connected undirected graphs with diameter d by ℱ_d.
For a directed graph 𝔛, the distance d_𝔛(u,v) of a vertex v from a vertex u is the length of a shortest directed path from u to v. The diameter of a directed graph 𝔛, denoted by diam(𝔛), is the number max_u,vd_𝔛(u,v). We write diam(𝔛):=∞ if there is no directed path from u to v for some pair of vertices u and v in 𝔛. Let X_ be the directed graph obtained from X after introducing the orientation . The oriented diameter OD(X) of X is defined to be the minimum number in the set {diam(X_)  |   is an orientation of  X}. Let OD(ℱ_d):=max {OD(X)  |  X∈ℱ_d}. Note that OD(X)=∞ if the graph X is not 2-edge connected[ 
We assume both the diameter and the oriented diameter of a graph with a single vertex to be 0.].     


While Robbins <cit.> provided the necessary and sufficient condition for the existence of a strong orientation of a graph, the paper does not offer any quantitative analysis of the difference in distances between a pair of vertices before and after strongly orienting the graph. In 1978, Chvátal and Thomassen <cit.> accepted this challenge and proved that 1/2 d^2 + d ≤ OD(X) ≤ 2d^2+2d for all X∈ℱ_d. In 2021, Babu et al. <cit.> improved the upper bound to 1.373d^2 + 6.971d - 1 for all d ≥ 8. Both of these works yield polynomial-time algorithms to obtain the required orientation.

The exploration of oriented diameters for classes of graphs with small values of diameter, as well as specific graph classes, was prompted by the quadratic upper bound on the oriented diameter. AT-free graphs <cit.> and chordal graphs <cit.> are popular such graph classes investigated. Attempts were also made to improve the general bound for OD(ℱ_d) provided by Chvátal and Thomassen <cit.> for specific values of d. From a result in <cit.>, it can be seen that OD(ℱ_1) = 3. Chvátal and Thomassen <cit.> proved that OD(ℱ_2) = 6. A tight bound was obtained for OD(ℱ_3) also. The results from <cit.> proved that OD(ℱ_3) = 9. However, exact bounds are not available when d > 3. The current best upper bound is 21, and the lower bound is 12 for OD(ℱ_4)  <cit.>. The upper and lower bounds for OD(ℱ_d) when d ≥ 5 also follow from these two works. Moreover, these results demonstrate the challenging nature of determining the oriented diameter for classes of graphs, even when the diameter is very small.

There are several classes of graphs defined in terms of groups, e.g., Cayley graphs, commuting graphs, power graphs, etc. Cameron's survey contains an interesting collection of results on such graphs <cit.>.  In this paper, we focus on power graphs of finite groups (<Ref>), which were defined by Chakrabarty et al. <cit.>.

 Abawajy et al. <cit.> and Kumar et al. <cit.> gave surveys on power graphs. 

Our primary motivation was to investigate if the symmetry structure of the underlying group of a power graph is useful for studying its oriented diameter. In this paper, we provide strong evidence that the algebraic structure is indeed helpful. 


The result of Chvátal and Thomassen <cit.> implies that OD(Pow(G))≤ 6 for all 2-edge connected power graphs, as Pow(G)∈ℱ_1 ∪ℱ_2 (see <Ref>). We obtain a tighter upper bound for power graphs by showing that every 2-edge connected power graph has oriented diameter at most 4. Moreover, the condition of Pow(G) being 2-edge connected simply translates to G not having any maximal cyclic subgroup of order 2.

Observe that ℱ_1 consists only of complete graphs K_n. A result in <cit.> proved that a complete graph K_n has oriented diameter 2 when n ≥ 3 and n ≠ 4. On the other hand, OD(K_4)=3.  A graph X ∈ℱ_d can have oriented diameter 2 only if d ∈{1, 2} because OD(X) ≥ diam(X).

We show that the power graph of a cyclic group of order n has oriented diameter 2 for all n≠ 2,4,6.  Until our work, to the best of our knowledge, no infinite family of graphs belonging to ℱ_2 with oriented diameter 2 had been identified. 

Nilpotent groups are important classes of groups that have been studied extensively (see, e.g., <cit.>).  We show that the oriented diameter of finite non-cyclic nilpotent groups is either 3 or 4. Moreover, we determine the exact conditions under which the oriented diameter is 3 and 4. Our main result in this paper is a complete group theoretic characterization of the oriented diameter of power graphs of nilpotent groups. We give this characterization in terms of the uniqueness of certain subgroups and the existence of a certain maximal cyclic subgroup.

    
Next, we focus on the computational problem of computing the oriented diameter of a given graph X.  A key result by Chvátal et al. <cit.> showed that it is NP-hard to decide whether a given undirected graph has oriented diameter 2. This leads to the investigation of several versions of the problem by restricting the class of graphs. 
 Fomin et al. provided an approximation algorithm to orient an AT-free graph X of diameter d with an orientation of diameter at most 2d+11 <cit.>. 

Fomin, Matamala and Rapaport <cit.> gave a linear-time approximation algorithm for computing a strong orientation for a chordal graph X with diameter at most one plus twice the oriented diameter of X. Eggemann and Noble <cit.>  designed a fixed-parameter tractable (FPT) algorithm that decides if a planar graph X has oriented diameter at most l, where l is the parameter.





We show that the oriented diameter of the power graphs of nilpotent groups can be computed in polynomial time. 

It turns out it is rather straightforward  to  check the conditions in the characterization of the oriented diameter of power graphs of finite nilpotent groups in polynomial time. 

Our results on the oriented diameter of power graphs hinge on figuring out interesting combinatorial and algebraic structures of the power graphs. For example, the results on the power graphs of cyclic groups depend on a careful “decomposition” of the graph in “layers” using its subgroup structures, which in turn helps us to apply an inductive approach for constructing a diameter 2 orientation (see <Ref>). 

The orientations we construct in this paper depend on careful designs of gadgets (P_4-gadget in <Ref> and C_4-gadget in  <Ref>) and their placements in Pow(G) using group theoretic properties (
<Ref>, 
<Ref>).
For a nilpotent group  G, we prove that for Pow(G) to have oriented diameter 3, the oriented edges of Pow(G) must obey certain uniformity conditions (<Ref>). While proving an important lower bound on OD(Pow(G)) for nilpotent group G, these conditions are crucial for cutting down the number of possibilities of orienting edges in Pow(G) (<Ref>).   

 

§ PRELIMINARIES

 
For a simple graph X=(V,E), the vertex set of X is denoted by V(X), and the edge set of X is denoted by E(X)
. For basic definitions and notations from graph theory, an interested reader can refer to any standard textbook (e.g., <cit.>). The induced subgraph of X on S⊆ V(X) is denoted by X[S].  We denote a path (both directed and undirected) from u_1 to u_k by the sequence of vertices u_1u_2… u_k. 




 
 



    Let X=(V,E) be an undirected graph. A subset ⊆ V× V is said to be a partial orientation of X if  is obtained from assigning exactly one direction to a subset E' of the edge set E. That is, for all {u,v}∈ E', either (u,v) or (v,u) is in .
    We use X_ to denote the directed graph (V,). Further, we denote the distance from a vertex x to a vertex y in the directed graph X_ by d_X_(x,y).




    If  is a partial orientation of an undirected graph X, then OD(X) ≤ diam(X_).

    
 

 The basic definitions and facts on group theory can be found in any standard book (e.g.,  <cit.>). In this paper, we only consider finite groups. A subset H of a group G is called a subgroup of G if H forms a group under the binary operation of G. This is denoted by H ≤ G.

The number of elements in a group G is called the order of the group, denoted by |G|. The order of an element g in G, denoted by o(g), is the smallest positive integer m such that g^m=e, where e is the identity element. 

A group G is called cyclic if G={g, g^2, …, g^m-1, g^m=e} for some g∈ G. The element g is called a generator of G, and we write G=⟨ g ⟩. The set of all generators of a cyclic group G is denoted by gen(G).
For a cyclic group G, |gen(G)|=ϕ(|G|), where ϕ is the Euler's totient function. Recall that ϕ(p_1^_1… p_k^_k)=p_1^_1-1(p_1-1)… p_k^_k-1(p_k-1), where p_i's are distinct primes and _i's are natural numbers.

A subgroup C of G is called a cyclic subgroup if C is cyclic. We call a cyclic subgroup C of G a maximal cyclic subgroup of G if C is not properly contained in any cyclic subgroup of G. 
We now state a well-known group theoretic fact that is used extensively in this paper.



 A finite cyclic group of order n has a unique subgroup (which is also cyclic) of order d for each divisor d of n. 



A group G is called a p-group if the order of each non-identity element is some positive power of p, where p is a prime. We denote the class of groups with prime power order by . 
 For a prime p, if p^m is the highest power of p such that p^m divides |G|, then a subgroup H ≤ G such that |H|=p^m is called a Sylow p-subgroup of G. The direct product of two groups G and H, denoted by G× H, is the group with elements  (g,h) where  g ∈ G and h ∈ H under the group operation (g_1,h_1)(g_2,h_2)=(g_1g_2,h_1h_2), where the co-ordinate wise operations are the group operations of G and H respectively. A finite group is called a nilpotent group if it is a direct product of its Sylow subgroups. Moreover, each Sylow subgroup is unique in a finite nilpotent group. 


We now give the definition of power graphs (see <cit.>). 


The power graph of a group G, denoted by Pow(G), is an undirected graph with vertex set G, and edge set E=  {{x,y}: y = x^m  for some integer m }.   


 
     If {x,y} is an edge in Pow(G), then either o(x)|o(y) or o(y)|o(x).
 
 Since e is a dominating vertex of Pow(G), diam(Pow(G))≤ 2.
 
 We define an equivalence relation ∼ on G as follows: for x,y∈ G, x∼ y if and only if ⟨ x ⟩ = ⟨ y ⟩, i.e., x and y generate the same cyclic subgroup of G. We call this equivalence class generator equivalence class (in short, ge-class). Let us denote the ge-class containing x under ∼ by [x]. Note that [x]=gen(x).
 
 So, all the elements of a ge-class are of the same order. We define the order of a ge-class by the order of any element belonging to the class. 
   One can easily notice that the size of a class [x] is ϕ(o(x)).

 In Pow(G) the following two facts hold:
    (i) Each ge-class [x] of G induces a complete subgraph of Pow(G);
    (ii) For two ge-classes [x] and [y], if an element x∈ [x] is adjacent to an element y∈ [y] in Pow(G), then every element of [x] is adjacent to every element of [y]. 
    
    Hence, in this case, it makes sense to say that [x] and [y] are adjacent in the graph Pow(G).

    This remark motivates us to formulate the following definition.


 
   Two distinct ge-classes [x] and [y] are called adjacent if x and y are adjacent in Pow(G).
 

In <Ref>, we have provided an extended preliminary.




§ ORIENTED DIAMETER OF POWER GRAPHS


We begin the section by stating a necessary and sufficient condition on a finite group for the existence of a strong orientation of the corresponding power graph. The main result of this section is that the oriented diameter of 2-edge connected power graphs is at most 4.

Now, we state one useful result regarding the oriented diameter of complete graphs that is required for our further discussion.

Fomin, Matamala and Rapaport <cit.> proved the following theorem about the oriented diameter of complete graphs. 

 <cit.> 
For every n ≥ 3, OD(K_n)=2 if n ≠ 4, and OD(K_4)=3. Moreover, for every n ≥ 5, 
every strong orientation of K_n with diameter 2 can be extended to a strong orientation of K_n+1 with diameter 2  and this extension can be constructed in linear time.



    A power graph is 2-edge connected if and only if the underlying group has no maximal cyclic subgroup of order 2.







    If a group G has a maximal cyclic subgroup ⟨ g ⟩ of order 2, then Pow(G) has a pendant vertex (a vertex with degree 1) g adjacent to identity, i.e., {e,g} is a bridge in Pow(G).

    For the other direction, let {u,v} be a bridge of Pow(G). Now, if none of u and v are identity, then the subgraph induced on {u,v,e} forms a cycle, which is a contradiction to the fact {u,v} is a bridge in Pow(G). We can assume without loss of generality that u=e. If v has a neighbour, say v', in the graph Pow(G), then {u=e,v,v'} makes a cycle, and this again leads to the contradiction that {u=e,v} is a bridge. So, we can assume that e is the only neighbour of v in Pow(G). This means ⟨ v ⟩={v,e} and v ∉⟨ g ⟩ for any g ∈ G ∖{e}. So, ⟨ v ⟩ is a maximal cyclic subgroup of order 2.



According to <Ref>, the power graph of ℤ_2, dihedral group D_2n  are not 2-edge connected and hence are not strongly orientable.



    Let X=(V, E) be an undirected graph with a dominating vertex e. Suppose V∖{e} can be partitioned into sets C_1,…, C_m such that each induced subgraph X[C_i] is a complete subgraph with at least two vertices, then OD(X) ≤ 4. 


r0.35

[scale=0.8]
(e) at (0,0);
(a) at (0,2);
(b) at (2,2);
(c) at (2,0);

(e) node[left][scale=1] e;
(a) node[left][scale=1] a;
(b) node[right][scale=1] b;
(c) node[right][scale=1] c;



[ line width=0.5mm,black,opacity=1] (e) – (a)  node[ currarrow, pos=0.5, xscale=1, sloped, scale=1] ;
[ line width=0.5mm,black,opacity=1] (e) – (b)  node[ currarrow, pos=0.25, xscale=1, sloped, scale=1] ;
[ line width=0.5mm,black,opacity=1] (e) – (c)  node[ currarrow, pos=0.5, xscale=-1, sloped, scale=1] ;
[ line width=0.5mm,black,opacity=1] (a) – (b)  node[ currarrow, pos=0.5, xscale=1, sloped, scale=1] ;
[ line width=0.5mm,black,opacity=1] (a) – (c)  node[ currarrow, pos=0.25, xscale=1, sloped, scale=1] ;
[ line width=0.5mm,black,opacity=1] (b) – (c)  node[ currarrow, pos=0.5, xscale=1, sloped, scale=1] ;





An orientation of K_4 with ecc(e)=2



 
    

Proof.  We claim that there is a partial orientation  of the given graph X such that the eccentricity  [The out-eccentricity of a vertex v of a directed graph  is the maximum distance from v to a vertex u in . The in-eccentricity of a vertex v of a directed graph  is the maximum distance from a vertex u in  to v. The eccentricity of a vertex v of  is the maximum of its out-eccentricity and in-eccentricity.] of e in  is 2. This will give us diam() ≤ 4, which in turn will imply that OD(X) ≤ 4 (due to <Ref>). 
     Therefore, it is enough to give a partial orientation of each induced subgraph X[C_i ∪{ e }],  such that the vertex e has eccentricity 2 in the oriented subgraph X[C_i ∪{ e }].

    We observe that for each i, C_i∪{e} induces a complete subgraph of X of size at least 3. If X[C_i ∪{ e }] is a complete subgraph of size n ≠ 4, then by <Ref>, we can orient the subgraph with diameter 2. In particular, e has eccentricity 2 with this orientation. 

    Otherwise, if C_i={ a,b,c } then we can give an orientation to the induced subgraph X[C_i ∪{ e }] (as shown in <Ref>) with  e  having eccentricity 2 in the oriented subgraph X[C_i ∪{ e}]. □





    The oriented diameter of Pow(G) is at most 4, where G is a finite group with no maximal cyclic subgroup of order 2.


Let S=G∖{e}. Our idea is to partition S into sets C_1,…, C_m such that the condition of <Ref> is satisfied.
To construct C_1, we pick a vertex g ∈ S such that o(g) >2. Such a vertex exists as G does not have any maximal cyclic subgroup of order 2. Let C_1=[g]. Inductively, assume that we have constructed C_1, …, C_l. In S ∖ (C_1 ∪…∪ C_l) we pick a vertex g such that o(g)>2. The process ends if there is no such element. Otherwise, let C_l+1=[g]. 

Let  C_1, …, C_m be the sets created at the end of the process. If S ∖ (C_1 ∪…∪ C_m) is non-empty, it consists of elements of order 2 only. Let y ∈ S ∖ (C_1 ∪…∪ C_m). Since ⟨ y ⟩ is not a maximal cyclic subgroup, y must be generated by some element g of order more than 2.  Let g ∈ C_i. Note that no other element y' ∈ S ∖ (C_1 ∪…∪ C_m) can be generated by any element in C_i. Otherwise, it implies that ⟨ g ⟩ contains two elements of order 2, which contradicts <Ref>. Now, as g generates y,  the ge-class [g] is adjacent to [y]={y} (by <Ref>). Hence, by <Ref>, C_i ∪{y} induces a clique. We update C_i by C_i ∪{y}. Thus, each y ∈ S ∖ (C_1 ∪…∪ C_m) can be merged to a unique C_j. Now, we apply <Ref> to conclude that OD(Pow(G))≤ 4. Note that if S ∖ (C_1 ∪…∪ C_m) is empty, then we can directly apply <Ref> to obtain the result.



§ ORIENTED DIAMETER OF POWER GRAPHS OF CYCLIC GROUPS


Each cyclic group of order n is isomorphic to _n, where  _n is the additive group of integers modulo n. 
 <Ref> tells that when n ≥ 3, Pow(_n) has at least two dominating vertices. Using this, we prove that Pow(_n), where n ≥ 3, can be given a partial orientation of diameter 3 (see <Ref>). 
 
  font=small
r0.45

[scale=0.35]






                


 
  [color=black!60, fill=black!5, very thick][rounded corners] (6,13) rectangle (16,15.5);
  (11,17) node[below][scale=1] _n∖{d_1,d_2};
  [black] (10,14) circle(2pt);
  (10,14) node[above][scale=1] u;
  [black] (12,14) circle(2pt);
  (12,14) node[above][scale=1] v;
 
 
 
 
 
 
 
 
 

    
 [black] (9,11) circle(4pt);
 (8.9,11) node[left][scale=1] d_1;
 
 [black] (13,11) circle(4pt);
 (13.1,11) node[right][scale=1] d_2;

 

(9,11) – (13,11) node[ currarrow, pos=0.5, xscale=1, sloped, scale=1]  ;
(10,14) – (13,11) node[ currarrow, pos=0.5, xscale=-1, sloped, scale=1]  ;
(10,14) – (9,11) node[ currarrow, pos=0.5, xscale=-1, sloped, scale=1]  ;
(9,11) – (12,14) node[ currarrow, pos=0.5, xscale=-1, sloped, scale=1]  ;
(13,11) – (12,14) node[ currarrow, pos=0.5, xscale=-1, sloped, scale=1]  ;




                

Illustration of a partial orientation of Pow(_n) with diameter 3. 


    
<cit.>
    Let G be a cyclic group. Then Dom(Pow(G)) consists of all elements in G, if G is of prime power order; otherwise Dom(Pow(G))=gen(G)∪{e}.




    The oriented diameter of Pow(ℤ_n) is at most 3, where n ≥ 3.


Proof. From <Ref>, we know that Pow(ℤ_n) has at least two dominating vertices since ℤ_n has ϕ(n)≥ 2 generators. Let d_1 and d_2 be two such dominating vertices. First we orient the edge {d_1,d_2} as (d_1,d_2). Then for any vertex u ∈ℤ_n ∖{d_1,d_2}, we orient the edges {u,d_1}, {u,d_2} as (u,d_1) and (d_2,u) respectively forcing  u,d_1,d_2 to form a directed cycle (see <Ref>). It is easy to see that the diameter of this oriented graph is 3.
□




Now, we present the main result on the oriented diameter of the power graphs of cyclic groups.


  The oriented diameter of Pow(_n) =
    
      0    if n=1
∞   if n=2

      3    if n=4,6

      2    otherwise
    


First, we discuss the case when n=6.


     The oriented diameter of Pow(ℤ_6) is 3.




 
      We prove here that Pow(ℤ_6) (<Ref>) cannot have oriented diameter 2. The cyclic group _6 has group elements . In any strong orientation, it can not be the case that all the edges incident to a vertex v are directed outwards from v or inwards to v. Now in the case when the vertex  in Pow(ℤ_6) has only one outward edge, we can assume without loss of generality that the directions given to the edges incident to  in the graph Pow(_6) are  and . Then, to have a directed path of length 2 from  to the vertices  , we need the following directed edges:  respectively. In that case, we can not have a directed path of length 2 from  to  (see <Ref>), and hence, Pow(_6) cannot have an orientation with diameter 3. The case when vertex  in Pow(ℤ_6) has only one inward edge is similar. Therefore, by  <Ref>, we have OD(Pow(_6))=3.   


We now present some tools and techniques which are necessary to prove <Ref>. First, consider the directed subgraph, which is a directed path of length 3, shown in <Ref>. We call it a `P_4-gadget'. As the name suggests, the `P_4-gadget' is a tuple of four vertices (a, b, c, d) with directed edges (a,b), (b,c), (c,d).







    For n≥ 4, there exists an optimal orientation of K_n having a P_4-gadget as a subgraph.


 <Ref> shows an  optimal orientation of K_4 with a P_4-gadget. Figure <ref> shows an optimal orientation of K_5 with a P_4-gadget. In both the figures, the subgraph formed by the directed edges (a,b), (b, c), and (c, d) gives the required P_4-gadget (marked in blue). By Theorem <ref>, this orientation of K_5 can be extended to obtain an orientation of K_n with diameter 2 for n≥ 6. 













    Let X=(V, E) be an undirected graph such that V=L_T ⊔ L_M ⊔ L_B (where ⊔  denotes disjoint union) and the following properties hold: (a) There is a partial orientation of X[L_T] with diameter at most 2; (b) |L_M| is even, |L_M|≥ 4, and L_M is a set of dominating vertices of X; (c) There is a partial orientation _B of the edges of X[L_B] and the edges in E(L_T, L_B) such that there is a directed path of length at most 2 between any two vertices a,b ∈ L_B using only the directed edges in _B. Then the oriented diameter of X is 2.



    We orient the graph X with the following partial orientations _α, _β, _γ (see <Ref>).

    _α: Since the set L_M induces a clique of size at least 4, by <Ref> there is an optimal orientation of X[L_M] having a P_4-gadget. In _α, we include this optimal orientation of X[L_M] along with the optimal orientation of X[L_T] (as per condition (a)) and _B (as per condition (c)).
         
    _β: Pick a P_4-gadget (a,b,c,d) in L_M. Then, for any u ∈ L_T, we put (u,a),(b,u),(u,c),(d,u) in _. Also, depending on the directions of the edges {a,d} and {b,c} given in _, we orient the edges between any vertex r ∈ L_B and a vertex in {a,b,c,d} such that r,b,c as well as r,a,d lie in a directed 3-cycle. For example, if (a,d) ∈_α, then we put (r,a),(d,r) in _β. See <Ref>.
        
          

     _γ: When |L_M|≠ 4, partition the set L_M∖{a,b,c,d} into disjoint pairs {v,w}. This partitioning is possible since |L_M| is even. Now, we orient the edges between any vertex r ∈ L_B and a vertex in {v,w} such that r,v,w lie in a directed 3-cycle. For example, if (v,w) ∈_α, then we put (r,v),(w,r) in _γ.
        
        
        The case when |L_M|=4 is slightly different and handled as shown in <Ref>.
        
    
  
We now show that using _α,_β and _γ, we indeed get OD(X)=2. 

Let X_ be the directed graph derived after orienting the edges of X using the partial orientations _,_,_γ.


    It is easy to see that using _, there is a directed path of length at most 2 between any two vertices of L_T (and L_B). The same applies for L_M if |L_M|≥ 5. Whereas, if |L_M|=4, we can see from <Ref> that {a,d} is the only pair of vertices in L_M such that _ gives a directed path of length 3 from a to d in X[L_M]. But since (d,a) is in _, we have the directed edges (a,r) and (r,d) for any vertex r∈ L_B while applying the rule of _. Hence, in this case, there is a directed path ard of length 2, which solves our purpose.
    
    From <Ref> it is clear that d_X_(r,u)=d_X_(u,r)=2 for any vertex u∈ L_T and for any vertex r∈ L_B. Moreover, for any vertex u∈ L_T, for any vertex y∈{a,b,c,d}⊂ L_M and for any vertex r∈ L_B, we have d_X_(u,y)=d_X_(y,u)=2 and d_X_(r,y)=d_X_(y,r)=2. Now since every vertex y of L_M∖{a,b,c,d} participates in a directed 3-cycle with any vertex r of L_B as well as with any vertex u of L_T, due to _ (see <Ref> ), we have d_X_(u,y)=d_X_(y,u)=2 as well as d_X_(r,y)=d_X_(y,r)=2. 
    
    Hence, diam(X_)=2 and by <Ref>, we have OD(X)=2.      


Let us state a useful fact about the structure of power graphs of cyclic groups.



   Let G be a cyclic group and x,y ∈ G. Then {x,y} is an edge of Pow(G) if and only if o(x) | o(y) or o(y)| o(x). Therefore S is a clique in Pow(G) if and only if o(x)|o(y) or o(y)|o(x) for all x,y ∈ S.



    If q≥ 3 is a prime, then the oriented diameter of Pow(ℤ_2^q^), , ≥ 1, is 2 except when (,,q)=(1,1,3) (i.e., for _6).







    In this proof, we use the fact that a cyclic group H has exactly ϕ(k) elements of order k for each divisor k of |H|. Let G=_2^q^. Let G_j be the subgroup of G of order 2^q^j, 1≤ j ≤ (Since G is cyclic, unique G_j exits by <Ref>.). The idea is to inductively show that if Pow(G_j) has oriented diameter 2, so does G_j+1. For this, we apply <Ref> with L_B=G_j, L_M=gen(G_j+1)={x | o(x)=2^q^j+1}, and L_T=G_j+1∖ (L_B∪ L_M)={x |  o(x)=2^kq^j+1,  0≤ k ≤ (-1)}. The proof is by induction on j. 
    
    
    There are two base cases:


Base cases:  

     
  1. (,q)≠ (1,3). Then, we use j=1 as the base case.

     
     We divide G_1 into three sets L_B={x|  o(x)=1  or  o(x)=2^k · q  where  0 ≤ k < }; L_M= gen(G_1)={x|  o(x)=2^· q}; L_T={x |  o(x)=2^k  where  1 ≤ k ≤}. Using <Ref>, L_B and L_T induce complete subgraphs and, moreover, the corresponding induced subgraphs are isomorphic to  K_2^-1(q-1)+1 and K_2^-1 respectively. | L_M|= ϕ(2^· q)=2^-1(q-1)≥ 4.

     
  2. (,)=(1,3). Then, we use j=2 as the base case. 

     
     We divide  G_2 into three sets L_B={x|  o(x)=2  or  2 · 3}; L_M= gen(G_2)={x|  o(x)=2 · 3^2}; L_T={x |  o(x)=3^k  where  0≤ k ≤ 2}. Using <Ref>, L_B and L_T induce complete subgraphs and, moreover, the corresponding induced subgraphs are isomorphic to K_3 and K_7 respectively. |L_M|= ϕ(2 · 3^2)=6.
     
 


Now we verify that in both cases, the sets L_B, L_M and L_T satisfy the conditions of <Ref>. Since, in the first case, (α,q) ≠ (1,3), |L_B| and |L_T| are not equal to 2,4 for any value of . So, in both cases, L_B and L_T are either singleton sets or induce complete subgraphs with oriented diameter 2. Hence, it is sufficient to take _B as the optimal orientation of X[L_B]. Moreover, in each case, since L_M=gen(G_j), L_M consists of dominating vertices of Pow(G_j) by <Ref>. Hence, by <Ref>, the oriented diameter of Pow(G_j) is 2.
     
 Inductive step: We assume that OD(Pow(G_j))=2 and want to show that OD(Pow(G_j+1))=2. For this, we divide G_j+1 into L_B, L_M and L_T as described in the proof sketch. Now using <Ref> in L_T, any element of order 2^k_1q^j+1 is adjacent to any element of order 2^k_2q^j+1, where 0≤ k_1 < k_2 ≤ (-1). Hence, Pow(G_j+1)[L_T] is a complete subgraph of size at least ϕ(q^2)≥ 6 that can be oriented with diameter 2. The set L_M=gen(G_j+1) contains dominating vertices of Pow(G_j+1). Moreover, as this is not the base case, |L_M|=ϕ(2^q^j+1)≥ϕ(2^2 · 3^2)=12. Therefore, by <Ref>, OD(Pow(G_j+1))=2.

Hence by mathematical induction Pow(G_) has oriented diameter 2.


We now state two group theoretic facts which are used in the proof of <Ref> and the proof of <Ref>. For a proof of <Ref>, one can refer to <Ref>.


Let G and H be two finite groups such that gcd(|G|,|H|)=1. If g_1 generates g_2 in G and h_1 generates h_2 in H, then (g_1,h_1) generates (g_2,h_2) in G× H.  






<cit.>
 If m and n are two relatively prime numbers, then _mn≅_m×_n. 



    Let H be a cyclic group such that Pow(H) has oriented diameter 2. If gcd(|H|,p)=1, where p≠ 2 is a prime, then  Pow(H×_p^α), α≥ 1, can be oriented with diameter 2.


First, we give a proof sketch of the lemma.





Let Γ=Pow(H×_p^α). We pick elements g_0,…, g_α∈_p^α such that o(g_i)=p^i. This gives a tower of subgroups {e}=g_0≤…≤g_α=_p^α, where e is the identity element of _p^. Let G_j=H×g_j. Since |H| and |g_j| are coprime to each other, by <Ref>, each G_j, 0 ≤ j ≤ is a cyclic subgroup of H ×_p^. These subgroups form a tower of cyclic subgroups G_0≤…≤ G_α. We note that H≅ G_0 and G_α=H×_p^α. By induction on j, we show that the induced subgraph Γ_j=Γ[G_j]=Pow(G_j) has oriented diameter 2. 

As Γ_0 ≅ Pow(H), we have  OD(Γ_0)=2. For the inductive step, we use <Ref>. Let  L_T=G_j-1. By the induction hypothesis, Γ_j[L_T]=Γ_j-1 has oriented diameter 2, i.e., condition (a) of <Ref> is satisfied. The set of generators of G_j is gen(H)× [g_j]. We pick L_M to be the set of generators gen(H)× ([g_j]∖{g_j}). Since j>0 and p ≠ 2, |[g_j]|=ϕ(p^j)≥ 2. Thus, L_M ≠∅. We finally set L_B=G_j∖ (L_T∪ L_M)=((H∖ gen(H))× [g_j])⊔ (gen(H)×{g_j}).  We show conditions (b) and (c) of <Ref> in the main proof.
 






Now we go into more details of the proof.

  We note that |H|∉{2,4} as Pow(H) has oriented diameter 2. Moreover, if |H|=3 then p≥ 5.   
    
The set L_M being a subset of generators of G_j consists of dominating vertices of Γ_j=Pow(G_j),  and |L_M|=|gen(H)|×|[g_j]∖{g_j}| is even since |gen(H)|=ϕ(|H|) is an even number (since |H|≠ 2).
 
Now we show conditions (b) and (c) of <Ref>. 


    
    The set L_M being a subset of generators of G_j consists of dominating vertices of Γ_j=Pow(G_j),  and |L_M|=|gen(H)|×|[g_j]∖{g_j}| is even since |gen(H)|=ϕ(|H|) is an even number (as |H|≠ 2).
    
    For L_M to satisfy the condition (b) of <Ref>, we also need that, |L_M| ≥ 4. As |H|≠ 2, we have |gen(H)| ≥ 2. But the situation when |gen(H)|=2 and |[g_j]|=2 is problematic since it yields |L_M|=2. Now |[g_j]|=2 happens only if p=3. But in that case, as gcd(|H|,p)=1 and |H| ≠ 2 or 4, |H| must have a prime factor greater than or equal to 5 or |H| must be divisible by 2^3. In that case, |gen(H)| ≥ 4 and hence, |L_M| ≥ 4.
    

    The rest of the proof involves showing that condition (c) of <Ref> is satisfied, i.e., there exists an orientation _B of the edges of Γ[L_B] and the edges in E(L_T, L_B) such that there is a directed path of length at most 2 between any two vertices using only the directed edges in _B.

  

Observe that, L_B =((H∖ gen(H))× [g_j])⊔ (gen(H)×{g_j}) ⊆ G_j∖ G_j-1. Let _H be an orientation of H  having diameter 2. Our idea is to mimic the orientation _H of H while being oblivious to the second component of a vertex in L_B. In other words, for pairs of vertices (u,g) and (v,g') in L_B, if (u,v) ∈_H we put ((u,g),(v,g')) in _B, else we put ( (v,g'), (u,g) ) in _B. Note that if {u,v} is an edge in Pow(H), then {(u,g), (v,g')} is an edge in Γ_j (This can be verified easily by using <Ref>.).

     
     
     Since there is a directed path of length at most 2 between two distinct vertices u and v in Pow(H), the newly added directed edges in _B imply a directed path of length at most 2 between two distinct vertices (u,g'_j) and (v,g”_j), where u ≠ v and g'_j may or may not be equal to g”_j. So, the only remaining case to handle is when u=v, i.e., a pair of vertices in (H ∖ gen(H))× [g_j]. Now, observe that for all u ∈ H ∖ gen(H), the set {u}× [g_j] ⊆ L_B is a clique (due to <Ref>). Now if |[g_j]| ≠ 2, we put the optimal orientation of Γ[{u}× [g_j]] (using <Ref>) in _B.

     Note that if |[g_j]| ≠ 2 or 4, for any a,b ∈{u}× [g_j], for all u ∈ H ∖ gen(H), we have a directed path of length at most 2. If |[g_j]|=2 or 4, there exist exactly two vertices a=(u,g_j), b=(u,g'_j) in each {u}× [g_j] such that d_Γ__B(a,b)=3 (where Γ__B is the directed graph (V(Γ),_B)). To solve this, we use the edges E(L_T,L_B). Let e' be the identity element of H×_p^α. Since e'∈ H×g_0 = G_0 ⊆ G_j-1, note that e' ∈ L_T and e' is adjacent to all the vertices in L_B. 
       Now for a fixed u ∈ H ∖ gen(H), we orient the edges {a,e'} and {b,e'} (depending on whether (a,b) ∈_B or (b,a) ∈_B) so that a,b,e' create a directed triangle in Γ__B. 
     We do this for all u ∈ H ∖ gen(H). This gives a directed path of length at most 2 for all the remaining pairs of vertices from L_B. Hence, condition (c) of <Ref> is satisfied. Now, we apply <Ref> and get an orientation of Γ_j.    
 

Now we are ready to prove the main result (<Ref>) of this section.




Proof of <Ref>.
The cases when n=1 and n=2 are easy to see. By <Ref> and observing Pow(ℤ_4)=K_4, we have OD(Pow(ℤ_4))=3. We have proved the case for n=6 in <Ref>. Using <Ref> and <Ref>, we get OD(Pow(G))=2 for a cyclic group G ∈  that is not ℤ_2 or ℤ_4.

Now, we are left with the case when n has at least two prime factors and n≠ 6. Let n=p_1^α_1 p_2^α_2p_3^α_3... p_k^α_k be the prime factorization of n, where p_1,p_2,…,p_k are distinct primes, _i's are positive powers and k≥ 2. By <Ref>, we can write ℤ_n= ∏_i∈ Sℤ_p_i^α_i×∏_i∉ Sℤ_p_i^α_i for any S⊆ [n]. One can check that by suitably picking a subset S of size at most 2, we can ensure that the oriented diameter of the power graph of  H=∏_i∈ Sℤ_p_i^α_i is 2. 


 In particular, we consider p_1 and p_2 the smallest and the largest prime, respectively. We take a recursive approach to achieve an orientation of Pow(ℤ_n) with diameter 2. If p_1=2, then we start with orienting the power graph of H=_2^_1p_2^_2 with diameter 2 by applying <Ref>. If p_1>2, then we start with orienting the power graph of H=_p_1^_1 with diameter 2. In the first case, we extend H recursively by _p_3^_3,…,_p_k^_k, and with (k-2) applications of <Ref>, we get OD(Pow(_n))=2. Whereas, in the second case, we extend H recursively by _p_2^_2,…,_p_k^_k, and with (k-1) applications of <Ref>, we get OD(Pow(_n))=2.  
  □
 

















§ ORIENTED DIAMETER OF POWER GRAPHS OF P-GROUPS


In this section, we study the oriented diameter of power graphs for finite non-cyclic groups from the class  (recall that ={ G  |  G  is a p-group for some prime p}). The main result of this section is <Ref>, where we fully characterize the group class .


The definition of generalized quaternion group Q_2^n of order 2^n can be found in any standard textbook of abstract algebra (for example, see <cit.>). We note that a generalized quaternion group of order 4n for any n can be defined. In this paper, we just need quaternion groups of order 2^n and a few facts about such groups, which we list below.

 <cit.>
   The generalized quaternion Q_2^n, n≥ 3 contains [Note that Q_2≅_2 and Q_2^2≅_4.] exactly one maximal cyclic subgroup ⟨ x ⟩ of order 2^n-1, and each element outside ⟨ x ⟩ is of order 4. 


Moreover, we use the following two statements; one is a lemma by Burnside (<Ref>, 1911) and one is a result from <cit.> in the proof of the next theorem.

<cit.>
    Let G be a p-group for a prime p, which is neither cyclic nor generalized quaternion. Then G has at least two subgroups of order p.


<cit.>
    Let G ∈. Then Pow(G)∖{e} is connected if and only if G is either cyclic or generalized quaternion.




    (1) Let G ∈ be neither cyclic nor generalized quaternion. If G has no maximal cyclic subgroup of order 2, then the oriented diameter of Pow(G) is 4  ; (2) The oriented diameter of Pow(Q_2^n) is 3, where Q_2^n, n≥ 3 is the generalized quaternion group.










(1)
     Let Γ= Pow(G). Due to <Ref>, it is sufficient to prove that OD(Γ)≥ 4. By <Ref>, we know that Γ∖{e} is disconnected and hence Γ∖{e} has at least two connected [A connected component of a graph is a maximal connected subgraph of the graph.] components C_1 and C_2. So, there is no undirected e-avoiding path [A path in Pow(G) for a finite group G is e-avoiding if it does not include the vertex corresponding to the identity element e of G.] between a vertex of C_1 and a vertex of C_2 in the graph Γ.

   Now we prove that, for any arbitrary orientation  of Γ, there are two vertices u_1∈ C_1 and u_2 ∈ C_2 such that d_Γ_(u_1,u_2) ≥ 4 (recall Γ_ denotes the directed graph (V(Γ),)). For that, let us consider two elements c_1 ∈ C_1 and c_2 ∈ C_2. Without loss of generality, let us assume that (c_1 ,e) ∈. If (e,c_2) ∈ then d_(c_2,e), d_(e,c_1) ≥ 2. Thus, we have d_(c_2,c_1) ≥ 4. For the other case, suppose (c_2,e) ∈. Now, to have d_(c_1,c_2) ≤ 3, we must have a vertex d in C_2 such that (e,d), (d,c_2) ∈. Analogously, to have d_(c_2,c_1) ≤ 3, we must have a vertex d' ∈ C_1 such that (e,d'), (d',c_1) ∈. This gives us d_(d',e), d_(e,c_2) ≥ 2 which implies d_(d',c_2) ≥ 4. So, using , there is no directed path of length at most 3 from d' ∈ C_1 to c_2 ∈ C_2. 








(2) <Ref> and <Ref> implies that Q_2^n has a unique subgroup, say y, of order 2 . Since any element in Q_2^n∖⟨ x ⟩ (see description of x in <Ref>) belongs to some maximal cyclic subgroup of order 4, there are 2^n-2^n-1/ϕ(4)=2^n-2≥ 2 (as n≥ 3) maximal cyclic subgroups of order 4 in Q_2^n. Hence Q_2^n has at least two maximal cyclic subgroups C_1, C_2 of order 4 and one cyclic subgroup C_3 of order 4 inside the maximal cyclic subgroup ⟨ x ⟩ such that the intersection C_i ∩ C_j={e,y}, 1≤ i < j ≤ 3, where y is the unique element of Q_2^n of order 2. Let the two elements of order 4 in C_i be c_i1 and c_i2 such that 1 ≤ i ≤ 3. Since C_i ∩ C_j={e,y} for i ≠ j, a path between a vertex c_ir, r=1,2 and a vertex in c_js, s=1,2 in Pow(Q_2^n) has to include e or y.

    

   
Let Γ = Pow(Q_2^n). First, we show that no orientation of Γ has diameter 2. For the sake of contradiction, let us assume that  be an orientation of Γ such that the diameter of Γ_

is 2. The directed path from c_11 to c_21 of length 2 in Γ_ must pass through e or y. Without loss of generality we assume that the path goes through e. The case when the directed path from c_11 to c_21 of length 2 in Γ_ passes through y can be dealt similarly.  Now, since the directed path from c_11 to c_21 of length 2 in Γ_ passes through e, we have (c_11,e), (e,c_21) ∈. In this case, the directed path from c_21 to c_11 of length 2 has to pass through y. Hence, we must have (c_21,y), (y,c_11) ∈. This also implies that (c_12,e), (e,c_22), (c_22,y), (y,c_12) ∈. Now, to have a directed path of length 2 from c_11 to c_31, we need (e,c_31) ∈. On the other hand, to have a directed path of length 2 from c_31 to c_21, we need (c_31,e) ∈. This means we can have a directed path of length at most 2 either from c_11 to c_31 or from c_31 to c_21, but not both. This contradicts the fact that the diameter of Γ_ is 2. 
   
As we have shown that OD(Pow(Q_2^n) ≥ 3, if we can give a partial orientation of Pow(Q_2^n) with diameter 3, then OD(Pow(Q_2^n) = 3 (by <Ref>). Now, we give a partial orientation of Q_2^n, n≥ 3 with diameter 3. <Ref> shows such a partial orientation  of Pow(Q_2^n). In <Ref>, C_1, C_2, …, C_m denote the maximal cyclic subgroups of order 4, where m = 2^n-2. Also, c_i1,c_i2 denote the elements of order 4 in C_i. Note that C_i ∩ C_j={e,y}, for 1≤ i < j ≤ m and C_i ∩⟨ x ⟩ = {e,y}. We partition the set ⟨ x ⟩∖{e,y} into two arbitrary non-empty subsets A and B (note that |x| = 2^n-1≥ 4). 
    
    


    We put (e,y) in . 
    For all a ∈ A and for all b∈ B we put the following directions in : (b,a), (y,b), (e,b), (a,e), (a,y). Moreover, we put the following directions in : (c_i1,e), (c_i1,y), (c_i2,c_i1), (e, c_i2), (y, c_i2), for each i, 1≤ i ≤ 2^n-2. From <Ref>, it is easy to observe that the diameter of Pow(Q_2^n) after giving orientation  is 3.

Hence, the theorem is proved.




§  ORIENTED DIAMETER OF POWER GRAPHS OF NILPOTENT GROUPS


 Since in the previous section we have dealt with non-cyclic finite groups of , in this section, we only consider finite non-cyclic nilpotent groups G such that G ∉. We fully characterize the oriented diameter of power graphs of all such groups in the main result (see <Ref>) of this section. We write π(G) to denote the set of all prime divisors of |G|. We start our discussion with a fact about finite nilpotent groups, which follows from two group theoretic facts: <Ref> and <Ref> (see <ref>).



     Let G be a finite nilpotent group and x,y ∈ G ∖{e} be two elements such that o(x) and o(y) are co-prime to each other. Then o(xy)=o(x)· o(y). Moreover, if M is any maximal cyclic subgroup of a finite non-cyclic nilpotent group G, then p divides |M| for all p ∈π(G).


We now classify the non-trivial ge-classes (defined in <Ref>) of a nilpotent group G into two types based on their orders.


 Base class: We call a ge-class [x] with order o(x) divisible by exactly one prime from π(G) a base class. An element from a base class is called a base element. Moreover, for a prime p ∈π(G), a base element is called a p-base element if its order is a positive power of p. We denote the set of all base elements by B and the set of all p-base elements by B_p for a prime p∈π(G).

 Non-base class: We call a ge-class with order divisible by at least two primes from π(G) a non-base class. We call an element from a non-base class non-base element. We denote the set of all non-base elements by NB.

 
In finite nilpotent groups, if [x] and [y] are two ge-classes of order p^k and q^l, respectively, where p and q are distinct primes, then [xy] is the ge-class of order p^kq^l and [xy]=gen(⟨ xy ⟩) (using <Ref>). Moreover, by <Ref>, [xy] is adjacent to both [x] and [y]. By <Ref>, it can be easily observed that a non-base class of order n is adjacent to exactly one base class of order p^i, i≥ 1 where p is a prime and p^i is a divisor of n.
 



The next lemma is similar to Theorem 2.6 <cit.>.


Let G be a non-cyclic nilpotent group with |G|=p^mq^n, where p and q are distinct primes[Note that the condition on |G| in <Ref> is not necessary, but it is enough for our further discussion and makes the presentation simpler.] 
 and m,n ≥ 1.  Let u,v ∈ G ∖{e} such that ⟨ u ⟩∩⟨ v ⟩ ={e } satisfying one of the following conditions: (i) Both u and v are p-base elements; (ii) Both u and v are q-base elements; (iii) Both u and v are non-base elements. Then, any e-avoiding shortest path between u and v in Pow(G) is of length 4.






    
    We first prove the following claim.
    
    Let P be any e-avoiding path between u and v in Pow(G). Then P (including u and v) must contain one p-base element and one q-base element. 


Proof of <Ref>: Let a,b ∈ G be two adjacent elements in Pow(G). If there exists a prime p which divides both o(a) and o(b), then ⟨ a ⟩∩⟨ b ⟩ contains a p-order subgroup (because a∩b is a cyclic subgroup and <Ref> holds). Now, let P: ug_1g_2… g_n v be an e-avoiding path between u and v. For the sake of contradiction, assume that every element/vertex of P has its order divisible by p. Then, we can say that ⟨ u ⟩∩⟨ g_1 ⟩∩…∩⟨ g_n ⟩∩⟨ v ⟩ contains a p-order subgroup. This contradicts the fact that ⟨ u ⟩∩⟨ v ⟩={e}. So, there is at least one element in P whose order is not divisible by p. In other words, a q-base element is in P. Similarly, we can say that P contains at least one p-base element.



We now go over the conditions of <Ref> one by one.

(i) Let o(u)=p^α, ≥ 1 and o(v)=p^α ', ' ≥ 1. From <Ref>, any e-avoiding path between u and v in Pow(G) contains at least one element a of order q^β, where β≥ 1. Now by <Ref>, a is not adjacent to either u or v in Pow(G). Hence, any shortest e-avoiding path between u and a is of length at least 2, and similarly, any shortest e-avoiding path between a and v is of length at least 2.

(ii) The proof is similar to (i).

(iii) Let  o(u)=p^αq^β, ,≥ 1 and o(v)=p^α 'q^β', ',' ≥ 1. From <Ref>, an e-avoiding path P between u and v in Pow(G), contains at least one element, say a, of order p^r, where r ≥ 1 and one element, say b, of order q^r', where r'≥ 1. Without loss of generality, we can assume that  uabv is a subpath of P. Now, an e-avoiding path between a and b is of length at least 2 (since a and b are not adjacent in Pow(G) by <Ref>). 
So, the length of P is at least 4.



The next lemma is crucial in cutting down the number of patterns for showing lower-bound of the oriented diameter of groups considered in <Ref>. 

(Uniformity lemma)
    Let G be a non-cyclic nilpotent group such that |G|=p^mq^n, where p and q are distinct primes and m,n ≥ 1. Let u,v ∈ G∖{e} such that ⟨ u ⟩∩⟨ v ⟩ = {e} satisfying one of the following conditions:
    (i) Both u and v are p-base elements ; 
    (ii) Both u and v are q-base elements ;
    (iii) Both u and v are non-base elements .
    In an orientation  of Pow(G) with diameter 3, if (u,e) ∈ then (v,e) ∈. Also, if (e,u) ∈ then (e,v) ∈.



    Using <Ref>, any undirected path between u and v of length at most 3 in Pow(G) must include identity e. So, in , we must include e in any directed path between u and v. We prove by contradiction that if (u,e) ∈ then (v,e) ∈. So, let us assume that (u,e) ∈ but (v,e) ∉. Now consider going from v to u. Since (v,e), (e,u) ∉,  both the directed paths from v to e and e to u are of at least length 2. This implies that any directed path from v to u is of length at least 4. Hence, this contradicts our assumption that  is of diameter 3. So, (u,e) ∈ implies (v,e) ∈. The reverse case is similar.
    



















  

 
 




















    For a finite non-cyclic nilpotent group G ∉,  the oriented diameter of Pow(G) is at least 3.






    A finite nilpotent group is a direct product of its Sylow subgroups. As G is non-cyclic, at least one such Sylow subgroup, say Sylow p-subgroup S_p is non-cyclic. 
    

    If S_p is not also generalised quaternion, then using <Ref>, we can say that S_p has at least two subgroups P_1 and P_2 of order p. Let P_1=g_1 and P_2=g_2. Now using <Ref>
    
    one can verify that g_1 and g_2 have no common neighbour other than e in Pow(G). Hence, we can conclude that Pow(G) cannot have an orientation of diameter 2.
    

    Now, let S_p=S_2=Q_2^n, n ≥ 3. From the proof of (2) of <Ref>, we know that S_2 has at least three distinct cyclic subgroups C_1,C_2,C_3 of order 4 such that C_i ∩ C_j ={e,y} where 1 ≤ i < j ≤ 3 and y is the unique element of order 2 in S_2. Now, similar to the proof of (2) of <Ref>, we can argue that e and y are the only common neighbours of any vertex of C_i and any vertex of C_j in Pow(G) and OD(Pow(G)) is at least 3.




We now characterise the nilpotent groups for which an oriented diameter of 3 is not possible in <ref>. For that, we use the following notations.

Subset Notations:
Let G be a non-cyclic nilpotent group and |G|=2^mp^n, where p is an odd prime and m,n ≥ 1. We use the notations [x_1],[x_2],…,[x_r] to denote the ge-classes of order 2 and the notations [y_1],[y_2],…,[y_s] to denote the ge-classes of order p. We partition the set B_2 of 2-base elements into sets X_i, 1 ≤ i ≤ r where  X_i={u |  u ∈ B_2  and   [x_i] ⊆}. Similarly, we partition the set B_p of p-base elements into Y_1,Y_2, …, Y_s. 
We partition the set of non-base elements of G into rs sets as follows: A_ij={u |  [x_i] ⊆ and  [y_j] ⊆} for 1 ≤ i ≤ r and 1 ≤ j ≤ s. 

 The following fact can be verified using <Ref> and the fact that the intersection of two cyclic subgroups is also a cyclic subgroup. Moreover, it is used to prove <Ref>.



    
    Let i≠ i', j ≠ j'. If u∈ A_ij, v ∈ A_i'j', then u∩v={e}.



The following two statements, one an easy observation about power graphs and the other a lemma by Frobenius (1895) <cit.>, are used in the proof of <Ref>.





     Let G be a group and x be an element of order p, where p is any prime. Then, for any element y  (≠ e) ∈ G such that {x,y} is an edge of Pow(G), we have x ∈y. 


 <cit.> The number of p-order subgroups in a finite group G is k· p +1, where k ≥ 0.












Let G ∉  be a non-cyclic nilpotent group. If G satisfies all of the following conditions: (a) |G|=2^mp^n, where p is an odd prime, m,n ≥ 1; (b) G has a maximal cyclic subgroup of order 2p^β, for some 1 ≤β≤ n; (c) G has at least two subgroups of order p; (d) G has at least two subgroups of order 2, then the oriented diameter of Pow(G) is 4.


 The proof is by contraction and is divided into two main steps: In Step 1, we show that if there is an orientation with diameter 3, then it must follow one of 8 general patterns, which is discussed below. In Step 2, we show that each of these 8 patterns gives a contradiction. As we will see, some of these patterns are just symmetric versions of other patterns.



    
   Step 1: We first note that all maximal cyclic subgroups of G are of order 2^m'p^n', m',n'≥ 1 (by <Ref>). Therefore, by <Ref>, Pow(G) has an orientation with diameter 4. Moreover, by <Ref>, OD(Pow(G))≥ 3. 
    We show that Pow(G) cannot have oriented diameter 3. For the sake of contradiction, let  be an orientation of Pow(G) with diameter 3.  We use the same notations A_ij, i∈{1,2,…,r} and j∈{1,2,…,s} as defined above. Since (c) and (d) hold, we note that r,s≥ 3 by <Ref>. We start by picking an element v∈ A_11. Without loss of generality, let (v,e)∈. We show that for any u∈ NB, we must have (u,e)∈. 
    
    Let u∈ A_ij where 1<i≤ r, 1<j≤ s. It is easy to see that u∩v= {e}, by <Ref>. So, using <Ref>, we have (u,e)∈. As u is arbitrarily chosen, we have (u,e)∈, for all u∈ A_ij where 1<i≤ r, 1<j≤ s. Now if u ∈ A_1j (or A_i1), we have a set A_kk where k∉{1,j} (or k ∉{i,1}), as r,s≥ 3.  Note that for  w ∈ A_kk, v∩w={e} and u∩w={e} (by <Ref>). So applying <Ref> to v and w gives  (w,e) ∈. Another application of <Ref> on u and w shows that (u,e)∈. As u is arbitrarily chosen, we have (u,e)∈ for all u∈ A_1j (or A_i1) where i ∈{1,2,…,r}, j ∈{1,2,…,s}. The case (e,v)∈ similarly implies that (e,u)∈ for all u∈ NB. 
    



Hence, we have either (u,e) ∈ for all u ∈ NB, or (e,u) ∈ for all u ∈ NB. We denote these by NB {e} and {e} NB, respectively. In general for an orientation  and two sets A and B, we write A  B, if (a,b)∈ for all a∈ A,b ∈ B.
    
    
    In a similar way, using <Ref>, we can show that either (u,e) ∈ for all u in the set B_2 of all 2-base elements (we use the shorthand B_2 {e} to denote this case) or  (e,u) ∈ for all u ∈ B_2 (denoted by {e} B_2). We can also show that either (u,e) ∈ for all u in the set B_p of all p-base elements (denoted by B_p {e}) or  (e,u) ∈ for all u ∈ B_p (denoted by {e} B_p).

    
    The above discussion shows that there are 8 possible patterns in . 

    

    
    Step 2: Now we will inspect all the patterns one by one.
    
    

Pattern 1: NB{e},  B_2{e},  B_p{e}. This pattern does not yield a strong orientation since there is no outward edge from e.

  Pattern 2: {e} NB,  B_2{e},  B_p {e}.
    In this pattern, any directed path containing e from any non-base element to any base element is of length at least 4. Now, we show that there exists at least a pair of vertices a and b such that we can not have a directed e-avoiding path from a to b of length at most 3.  By condition (b), G has a maximal cyclic subgroup C of order 2p^β, for some 1 ≤β≤  n. Now, by condition (c), G has at least two subgroups of order p. Hence by <Ref>, G has a subgroup v of order p such that C ∩v={e}. We need the following claim.
    

    
    
        Let C be a maximal cyclic subgroup of G of order 2p^β, β≥ 1. Let u be a non-base element in C and v be an element of order p not in C. Then, there is no e-avoiding path between u and v of length at most 2 in Pow(G). Moreover, if P: uw_1w_2 v is an e-avoiding path of length 3 between u and v in Pow(G), then w_1 has to be the unique element of order 2 in C.
    
   Proof of <Ref>:
         Let x and y be elements of order 2 and p in C. Then by <Ref>, y≤u≤ C. First, we show that there is no e-avoiding path between u and v of length at most 2 in Pow(G). Since u does not generate v, by <Ref>, {u,v} is not an edge. Now, if possible, let w≠ e be a common neighbour of u and v. By <Ref>, v ∈w and v≤w. Moreover since C ∩v={e}, we must have u ∈w (Otherwise w ∈u, which together with the fact v ∈w implies that  v ∈u.) and u≤w and y≤w. This contradicts <Ref>. Hence any e-avoiding path between u and v in Pow(G) is of length at least 3. 

    At first, observe that if o(w_1)=2^ for some α≥ 1, then[This is because in Pow(G) if an element x whose order is prime power is adjacent to an element y whose order is non-prime power, then x ∈y.] w_1 ∈u⊆ C. Now, as o(w_1) divides |C| (since the order of an element of a finite group divides the order of the group), we have o(w_1)=2 and hence w_1=x. So, to prove the claim, it is enough to show that p does not divide o(w_1). For the sake of contradiction, let p| o(w_1). 
        
        If w_1 ∈u, then w_1 is a subgroup of u and C. Also, as p| o(w_1), by <Ref>, w_1 contains a unique subgroup of order p. So, y≤w_1. If u ∈w_1, then y≤u≤w_1. Hence y≤w_1 in both the cases. 
        
        To have an e-avoiding path P of length 3 from u to v, we must have a non-identity vertex, which is a common neighbour of w_1 and v. Let w_2 be a common neighbour of w_1 and v. As {w_2, v}∈ Pow(G) and o(v)=p, by <Ref>, we have v ∈w_2. 
        
        Now, the edge {w_1,w_2} implies w_1 ∈w_2 or w_2 ∈w_1. If w_1 ∈w_2 then w_2 contains w_1. This implies w_2 contains two distinct subgroups y and v of order p, which is a contradiction to <Ref>. Also, if w_2 ∈w_1, then v ∈w_1 (since v ∈w_2) and v≤w_1. Again, this contradicts <Ref>. So, p does not divide o(w_1). Hence, the claim is proved. 

    

        Let C_1 be a maximal cyclic subgroup of order 2p^β containing x as the unique 2 order element and y_1 as a p order element. Let u_1 be a non-base element of C_1. Let v_2 be an element of order p outside C_1. Using <Ref>, any directed e-avoiding path of length 3 from u_1 to v_2 must use the edge (u_1,x). So, the path should be of the form: u_1xgv_2, where g is some element such that g contains both x and v_2 (by <Ref>) [Note that g is a non-base element.].  So, to have a directed e-avoiding path from u_1 to v_2 of length 3, we must have (x,g) ∈ for some non-base element g outside C_1. Now if C_2 is a maximal cyclic subgroup containing g (and hence containing x), then by <Ref> (see <Ref>), |C_2|=2p^β', for some β' ≥ 1. Now, to have a directed e-avoiding path from g to y_1 of at most length 3, by using <Ref>, we must put (g,x) ∈. This clashes with our previous requirement of (x,g) ∈. Hence, this pattern is not possible in .


    Pattern 3: NB{e}, {e} B_2, B_p{e}. Let y and y' be two p-base elements such that [y]≠ [y'], i.e., y∩y' = {e}. Using <Ref>,  we can conclude that a directed path P from y to y' of length 3 must pass through e. Moreover, since B_p{e}, P must have (y,e).
    
    Note that the only outward edges from e are towards the 2-base elements. Also, any directed path from a 2-base element to y' is of at least length 2. This is because y' is a p-base element, and by <Ref>, a 2-base element and a p-base element can not be adjacent in Pow(G). Therefore, the length of a directed path from y to y' is at least 4. Hence, we cannot have an orientation with diameter 3.

    Pattern 4: NB{e}, B_2 {e}, {e} B_p. As done in Pattern 3, we can similarly argue that there is no directed path of length at most 3 from x to x', where x and x' are 2-base elements and [x]≠[x'].

    The last four patterns are symmetric to the first four patterns and can be dealt with using the following simple observation.


    
Let 𝔛 =(V,E) be a directed graph. Also, let 𝔛_rev=(V, E_rev) be the directed graph where E_rev is the set of edges obtained by reversing the directions of all the edges in E. Then diam(𝔛)=diam(𝔛_rev).

Let  be a partial orientation of an undirected graph X=(V,E) and X_ be the directed graph (V,). Moreover, let A ⊆. If diam(X_)=d, then there exists a partial orientation ' of X containing A_rev such that diam(X_')=d.




     Pattern 5: {e} NB,  {e} B_2,  {e} B_p. By <Ref>, this is symmetric to Pattern 1. By `symmetric', we mean that getting a partial orientation containing Pattern 5 with diameter 3 would imply that there is a partial orientation containing Pattern 1 with diameter 3.
    
    Pattern 6: {e} NB,  B_2{e},  {e} B_p. By <Ref>, this is symmetric to Pattern 3.
    

    Pattern 7: {e} NB,  {e} B_2,  B_p {e}. By <Ref>, this is symmetric to Pattern 4.
    

    Pattern 8: NB {e}, {e} B_2,  {e} B_p. By <Ref>, this is symmetric to Pattern 2.


    So we have shown that none of the 8 patterns is satisfied in an orientation of Pow(G) with diameter 3. Hence, it is proved that if G satisfies the given conditions (a)-(d), then an orientation of Pow(G) with diameter 3 is not possible.


We now state the main result on the oriented diameter of power graphs of finite non-cyclic nilpotent groups which are not in .




    Let G ∉ be a finite non-cyclic nilpotent group. Then the oriented diameter of Pow(G) is 3 if and only if G satisfies at least one of the following conditions: (a) |G| is divisible by at least two distinct odd primes; (b) G has no maximal cyclic subgroup of order 2p^β, 1≤β≤ n, where p is an odd prime; (c) G has unique p-order subgroup, where p is an odd prime; (d) G has unique 2-order subgroup. Otherwise, the oriented diameter of Pow(G) is 4.
    
    
    
    
    
    


Examples of groups for each of the conditions are in  <Ref>. We first state the following four lemmas: <Ref>, <Ref>, <Ref> and <Ref>, which are used to prove the above theorem.


    Let G be a non-cyclic nilpotent group. If |G| is divisible by at least two distinct odd primes, then the oriented diameter of Pow(G) is 3.


 
    Let G be a non-cyclic nilpotent group of order 2^mp^n, where p is an odd prime and m,n ≥ 1.  If G has no maximal cyclic subgroup of order 2p^β, 1≤β≤ n, then the oriented diameter of Pow(G) is 3.



    Let G be a non-cyclic nilpotent group and |G|=2^mp^n, where p is an odd prime and m,n ≥ 1. If G has unique subgroup of order p, then the oriented diameter of Pow(G) is 3.



 
    Let G be a non-cyclic nilpotent group and |G|=2^mp^n, m, n ≥ 1, where p is an odd prime. If G has a unique subgroup of order 2, then the oriented diameter of Pow(G) is 3.




Proof of <Ref>. If G does not satisfy any of the conditions (a)-(d), then by <Ref>, we have OD(Pow(G))=4. Now consider the opposite direction. The case when G satisfies condition (a) is handled in <Ref>. Now note that for the remaining cases, i.e., when G satisfies condition (b) or (c) or (d), it is enough to consider |G|=2^mp^n, where p is an odd prime and m,n ≥ 1. Hence, by applying <Ref>, <Ref> and <Ref>, the oriented diameter of Pow(G) is 3 when G satisfies condition (b), (c) and (d) respectively.
□




We now prove <Ref> and <Ref> in the rest of this section. The proof techniques of <Ref> and <Ref> are almost similar to <Ref>, and hence, we have put the proofs of these two lemmas in <Ref> and <Ref> respectively. Now due to <Ref> and <Ref>, in order to prove each of the four lemmas, it is enough to give a partial orientation of diameter 3. The partial orientations used in <Ref>, <Ref> and <Ref> are different but involve some common partial orientations, namely _1,_2 and _3. These common partial orientations are described in <Ref> below. In <Ref>, we prove that _2 and _3 themselves can establish directed paths of length at most 2 between certain sets of vertices. In each of the three lemmas: <Ref>, <Ref> and <ref>, we augment ∪_i=1^3 _i with suitable partial orientations. Whereas, in <Ref> we design a completely different partial orientation.





Let G ∉ be a non-cyclic nilpotent group. The descriptions of partial orientations _1,_2,_3 of Pow(G) are as follows:    

r0.45

    [scale=0.35]
    
 
 
 
 
 
        
        (a) at (2,7);
        (b) at (3,11);
        (c) at (4,7);
        (d) at (4.1,11);
        (e) at (10,7);
        (f) at (10,11);
        (g) at (12,7);
        (h) at (11.1,11);

    
        
        [color=black!50, fill=black!10, very thick][rounded corners] (1,9.7) rectangle (13,13.5);
         [color=brown!80, fill=brown!50, very thick][rounded corners] (1,5) rectangle (3,7);
        [color=brown!80, fill=brown!50, very thick][rounded corners] (3,5) rectangle (5,7);
        [color=teal!80, fill=teal!40, very thick][rounded corners] (9,5) rectangle (11,7);
        [color=teal!80, fill=teal!40, very thick][rounded corners] (11,5) rectangle (13,7);

        
         [color=brown!80, fill=brown!50, very thick][] (3.5,11) ellipse (1.5cm and 1cm);
         [color=teal!80, fill=teal!40, very thick][] (10.6,11) ellipse (1.5cm and 1cm);
        
        
        
        [brown] (3,11) circle(4pt);
        [brown] (4.1,11) circle(4pt);
        [teal] (10,11) circle(4pt); 
        [teal] (11.2,11) circle(4pt); 

        (3,11.5) node[][scale=0.8] n_1;
        (4.2,11.5) node[][scale=0.8] n_2;
         (10.2,11.5) node[][scale=0.8] n_1';
        (11.4,11.5) node[][scale=0.8] n_2';

        
        
        (1,6) node[right][scale=0.8] M_1;
        (3,6) node[right][scale=0.8] M_2;
        (9,6) node[right][scale=0.8] M_1';
        (11,6) node[right][scale=0.8] M_2';
        
        [brown, thick] (a) – (b) node[ currarrow, pos=0.5, xscale=0.6, sloped, scale=-1, color=brown]  ;
        [brown, thick] (b) – (c) node[ currarrow, pos=0.5, xscale=0.6, sloped, scale=-1, color=brown]  ;
        [brown, thick] (c) – (d) node[ currarrow, pos=0.5, xscale=0.6, sloped, scale=-1, color=brown]  ;
        [brown, thick] (d) – (a) node[ currarrow, pos=0.5, xscale=-0.6, sloped, scale=-1, color=brown]  ;

       [teal,thick] (e) – (f) node[ currarrow, pos=0.5, xscale=-0.6, sloped, scale=1]  ;
       [teal,thick] (f) – (g) node[ currarrow, pos=0.5, xscale=-0.6, sloped, scale=1]  ; 
       [teal,thick] (g) – (h) node[ currarrow, pos=0.5, xscale=0.6, sloped, scale=1]  ; 
       [teal,thick] (h) – (e) node[ currarrow, pos=0.5, xscale=0.6, sloped, scale=1]  ; 
       
 
        [ line width=0.6mm,color=brown!90] (2,7) .. controls (-2,11) and (1.5,12) .. (3,13) node[ currarrow, pos=0.5, xscale=1, sloped, scale=1, color=brown] ;
        [ line width=0.6mm,color=brown!90] (4,7) .. controls (8,9) and (7,11) .. (6,12) node[ currarrow, pos=0.5, xscale=1, sloped, scale=1, color=brown] ;
        
         [ line width=0.6mm,color=teal!80] (10,7) .. controls (6,9) and (8,12) .. (8,12) node[ currarrow, pos=0.45, xscale=-1, sloped, scale=1, color=teal] ;
        [ line width=0.6mm,color=teal!80] (12,7) .. controls (15,9) and (14,11) .. (12,13) node[ currarrow, pos=0.5, xscale=-1, sloped, scale=1, color=teal] ;
        
        
        (7,14.25) node[][scale=1] Non-base class N of order p^q^, ,≥ 1;
        (2.5,4) node[][scale=1] Base class M;
        (2.5,3) node[][scale=1] of order p;
        (12.2,4) node[][scale=1] Base class M'; 
        (12.2,3) node[][scale=1] of order q;

              
         
        Illustration of _2. The directed edges of E({n_1,n_2}, M_1 ∪ M_2) and E({n'_1,n'_2}, M'_1 ∪ M'_2) form two C_4-gadgets.
         



 _1 : From all u ∈ NB, we orient the edges towards e as (u,e). Also, from e, we orient the edges towards all u ∈ B as (e,u). 


_2 :  At first, we arbitrarily partition each base class M of odd prime order into two non-empty subsets M_1 and M_2. Let N be a non-base class and p be an odd prime divisor of the order of N. Due to <Ref>, N is adjacent to exactly one base class M of order p.  
At first, we mark two elements of N as n_1,n_2 (choices of n_1 and n_2 depend on M, as discussed in the note below). 
        
        Now, we make directed 4-cycles in the edges of E(N,M) (see <Ref>) as follows:  For all u_1 ∈ M_1 and u_2 ∈ M_2 we put (n_1,u_1), (u_1,n_2), (n_2,u_2), (u_2,n_1) in _2. We call the directed subgraph formed by the directed edges of E({n_1,n_2},M_1∪ M_2) due to _2 - `C_4-gadget'. This naming is due to the presence of several directed C_4 in E({n_1,n_2},M_1∪ M_2) after _2. Moreover we call n_1,n_2 the gadget anchor points in N for M.
        Now, the edges in E(M,N) of the form {u,v}, where u∈ M and v ∈ N∖{n_1,n_2} are  oriented as (u,v).


        Note:  While introducing  _2, we choose a disjoint pair of gadget anchor points in N for each base class  M of odd prime order adjacent to N. This is possible as the number k of base classes of odd prime order adjacent to N equals the number of odd prime divisors of r, where r is the order of N and also noting that |N|=ϕ(r)>2^k≥ 2k. 
        
       
        
_3: From any base element of order p^, ≥ 2, where p is an odd prime in π(G), we orient the edges towards all the adjacent non-base elements.








    Let G ∉ be a finite non-cyclic nilpotent group and p,q be two odd prime divisors of |G|. Then using partial orientations _2, _3 as stated in <Ref>, we have the following:
    
    (1) There is a directed path of length 2 between any vertex of a base class of order p and any vertex of a base class of order q using _2, where p and q are distinct.


    (2) There is a directed path of length at most 2 from any vertex of a base class of order p^, ≥ 2 to any vertex of a base class of order q, using _3 and _2, where p and q may or may not be distinct.




    We only prove (1) as (2) is similar.  Let M and M' be two base classes of order p and q, respectively. Then, we need to show that between any pair of vertices m ∈ M and m' ∈ M', there is a directed path of length 2. 
    As G is a nilpotent group, mm' is a non-base element (by <Ref>). Let N be the non-base class [mm']. Since mm' is adjacent to both m and m' in Pow(G), N is adjacent to both the base classes M and M' (by using <Ref>). Hence, we have oriented the edges in E(N,M) and E(N,M') as described in _2. 

    Let n_1,n_2 be the gadget anchor points in N involved in the C_4-gadget with M. Also, let n_3, n_4 be the gadget anchor points in N involved in the gadget with M'. From our discussion in <Ref>, the vertices n_1,n_2,n_3,n_4 are distinct. Now, for any m' ∈ M', we have either (n_3,m') or (n_4,m'). Also, as n_3 and n_4 are not involved in the C_4-gadget with M, we have (m,n_3) and (m,n_4) for all m ∈ M. Hence, we have a directed path of length 2 from any m ∈ M to any m' ∈ M' via n_3 or n_4. 
    




    Let G be a finite nilpotent group such that the set of prime divisors π(G) contains 2 and at least two distinct odd primes p and q. Then using <Ref>, any element of order 2^,  ≥ 1 and any element p^,  ≥ 1 have one common neighbour of order 2^p^q in Pow(G).






   
  Proof of <Ref>: Due to <Ref> and <Ref>, it is sufficient to give a partial orientation of Pow(G) with diameter 3. For that purpose, if |G| is even, then along with partial orientations _1,_2,_3 as stated in <Ref>, we use the following partial orientations (see <Ref>). If |G| is odd, we will see below that the partial orientations _1,_2 , _3 are sufficient.

   
    _4: From any base element of order 2, we orient the edges towards all the adjacent non-base elements of order 2^αp^β, where p is any odd prime in π(G) and α, β≥ 1.
    
      _5: Let N be a non-base class of order 2^αt, where ≥ 2 and t  (≠ 1) is co-prime to 2. Also, let M be the unique base class of order 2^2 that is adjacent to N. We orient the edges in E(N,M) similarly to _2 as stated in <Ref>. Here also, the choices of gadget anchor points of N for M depend on M as in <Ref>. In other words,  while introducing _5 in a non-base class N of order 2^αt, where ≥ 2 and 2 ∤ t, we select a pair of gadget anchor points {n_1,n_2} in N for the base class of order 2^2 adjacent to N in such a way that neither n_1 nor n_2 has been used as gadget anchor point in N while introducing _2. This is possible as the number k of base classes of odd prime order adjacent to N equals the number of prime divisors of t, and |N|=ϕ(2^t)>2^(k+1)≥ 2(k+1).

      _6: From any base element of order 2^, ≥ 3, we orient the edges towards all the adjacent non-base elements. Note that these non-base elements are of order 2^δt, where δ≥ and t  (≠ 1) is co-prime to 2.
   
       _7: From any non-base element of order 2p^q^, ,≥ 1, where p and q are any two distinct odd primes in π(G), we orient the edge towards the adjacent unique base element of order 2.
       

 



  

We show an illustration of the introduced partial orientations in <Ref>. 
The set B is partitioned into three subsets as follows: (a) R_1: consisting of the elements of order 2; (b) R_2: consisting of the elements of order 2^2 and p, where p is any odd prime in π(G); (c) R_3: consisting of the elements of order 2^, ≥ 3, and p^, ≥ 2, where p is any odd prime in π(G). Note that if |G| is odd, then G has no 2-base element. Hence, the region R_1 does not exist, whereas R_2 and R_3 only contain p-base elements, where p is an odd prime in π(G).















    Path directions: 
    First, we list down some necessary observations, which can be argued similarly to the proof of <Ref>. We also use <Ref> for discussing path directions. In the following observations, p is an odd prime in π(G).

    
        Note 1: 
        
        There is a directed path of length 2 from any element of order 2^α to any element of order p, using partial orientation _4 (when α=1) or _5 (when α=2) or _6 (when α≥ 3) along with partial orientation _2.


    
       Note 2: 
       
       There is a directed path of length 2 from any element of order p^β,  β≥ 2 (or, of order p) to any element of order 2 by noting <Ref> and using _3 (or _2) together with _7.
    
    
 Let Γ=Pow(G) and  denote the disjoint union of _1,…,_7 (or _1,…,_3 as required). Then,  we use the notation Γ_ to denote the directed graph (V(Γ),). 
 Moreover, let d(a,b) (we use d(a,b) instead of d_Γ_(a,b) as Γ and  are fixed in this context) denote the shortest distance from a vertex a to a vertex b in the directed graph Γ_ and d(a,S)=min{d(a,s) : s ∈ S} denote the shortest distance from a vertex a to a set S in Γ_. 


From <Ref>, one can see that d(v,e)=1 for any non-base element v and d(e,u)=1 for any base element u. This also implies that d(v,u)≤ 2, i.e., there is a directed path of length at most 2 from any element v∈ NB to any element u∈ B.


We claim that if u ∈ B=R_1∪ R_2∪ R_3, then d(u,NB)=1. For this, observe that if u ∈ R_1, then there exists some v∈ NB such that (u,v) ∈_4. Similarly, if u ∈ R_2, then there exists some v ∈ NB such that (u,v) ∈_2∪_5 and if u ∈ R_3, then there exists some v ∈ NB such that (u,v) ∈_3 ∪_6. 


Noting d(u,NB)=1 for all u∈ B and (v,e)∈_1 for all v∈ NB, we have a directed path of length at most 2 from any element of B to e. Combining such a path with (e,u') ∈_1, where u' is any element in B, we get a directed path of length at most 3 between any two elements of B.


 Now, for any non-base element v∈ NB, there exists at least one element u ∈ R_2 such that (u,v)∈_2. Moreover since (e,u)∈_1 for all u∈ R_2 ⊆ B, we have d(e,v) = 2 for all v∈ NB. Now, as (v',e)∈_1 for all v'∈ NB, we get d(v',v) ≤ 1+d(e,v) = 3, i.e., there is a directed path of length at most 3 between any two elements in NB. 









Now, we discuss the remaining case, i.e., when the source vertex u is from B, and the destination vertex v is from NB. Since v is a non-base element, o(v) always has at least one odd prime divisor, and hence there exists an element a∈⟨ v ⟩ such that o(a) is an odd prime. So the base class [a] is in R_2 and participates in a C_4-gadget with the non-base class [v] due to _2 (see <Ref>). Now, if o(u)=2^α ,α≥ 1, then using Note 1, we have d(u,a) ≤ 2 for all a ∈ [a]. Further using the C_4-gadget between [a] and [v], we have d(u,v) ≤ 3. Now the case o(u)=p^β, β≥ 1 (where p is an odd prime) is divided into two subcases according to the number of distinct odd prime divisors of o(v). The first subcase is when o(v) is divisible by at least two odd primes p and q. Then, there exists an element c ∈v of order q, and hence, there is a C_4-gadget between [c] and [v] due to _2. Therefore, using the directed path of length 2 from u to any element of [c] as described in <Ref> and the gadget between [c] and [v], we have d(u,v) ≤ 3. Now, consider the second subcase, i.e., when o(u)=p^β, β≥ 1 and o(v) is divisible by only two primes 2 and p. If w is the (unique) element of order 2 in v, then Note 2 implies d(u,w)≤ 2. Moreover, since w ∈ R_1, we have (w,v) ∈_4. This gives us d(u,v) ≤ 3 in this case.□










Proof of <Ref>: Due to <Ref> and <Ref>, it is sufficient to give a partial orientation of Pow(G) with diameter 3. The maximal cyclic subgroups of G are of order 2^αp^β, where 1≤≤ m, 1≤≤ n and (,) ≠ (m,n) (by <Ref>). Now, if G has no maximal cyclic subgroup of order 2p^k for any 1 ≤ k ≤ n, then we can use <Ref> to prove that OD(Pow(G))=3.

     Now we consider the case when G has a maximal cyclic subgroup of order 2p^k, for some 1≤ k ≤ n.
     Let x be the unique subgroup of order 2 of G. Since every maximal cyclic subgroup of G contains x, by <Ref>, one can see that each maximal cyclic subgroup of G is of order 2p^β, 1 ≤β≤ n. Note that, here G=_2× S_p, (where S_p is the Sylow p-subgroup of G) due to Burnside's lemma (see <Ref>).
     
     

     Now we claim that in G, a base class M_i of order p^i is adjacent to exactly one non-base class N_i of order 2p^i (see <Ref> for the definition of two ge-classes being adjacent). 
     One can verify this by using the facts that G has a unique subgroup of order 2, and the intersection of two cyclic subgroups is a cyclic subgroup. On the other hand, using <Ref>, one can verify that each N_i is adjacent to exactly one M_i.
     
     So, there is a matching between the ge-classes of order p^i and 2p^i for all 1 ≤ i ≤ n in G. Let C_ij = M_ij∪ N_ij, where M_ij and N_ij denote the j-th ge-class of order p^i and 2p^i (since G is not cyclic, j>1 for at least one i). Analogously, we match the elements e and x (recall that x is the unique element of G of order 2) and put them in C_0. Now observe that G can be viewed as a disjoint union of C_0 and the sets C_ij, where 1≤ i ≤ n and 1< j. We also partition each N_ij in two non empty subsets {a_ij}, where a_ij is an arbitrary element of N_ij and B_ij=N_ij∖{a_ij} (this can always be done since |N_ij|≥ 2). We now describe a partial orientation   in which we orient a subset of the edges in the subgraph induced by the set C_0 ⊔ C_ij=C_0⊔({a_ij}⊔ B_ij⊔ M_ij), for each i and each j as follows:
     
     

         
         

         
        :  In this partial orientation, we put the following directed edges:
        
         (i) (a_ij,b), (e,b) and (b,x), for all b ∈ B_ij;
         
         (ii) (a_ij,e), (e,x) and (x,a_ij);
         
         (iii) (v,u), for all v ∈ N_ij and for all u ∈ M_ij.
         
         See <Ref> for an illustration of .

        
        
        
        
        


    Path directions:    
     From <Ref>, it can be observed that using , there is a directed path of length at most 2 between any vertex of C_0 and any vertex of C_ij, for any i and any j. 
    
    Note that any vertex c ∈ C_ij has an outward edge either (c,e) to e or (c,x) to x (Recall that x is the unique element of order 2.). Now, we want to exhibit a directed path of length at most 3 between two vertices c ∈ C_ij and c' ∈ C_i'j' where i,i',j,j' are non-zero indices and i (respectively j) may or may not be equal to i' (respectively j'). Without loss of generality, let (c, e) ∈ (The other case can be argued similarly.). Then, we can use the edge (c,e) together with the path from e to c' to have a path from c to c' of length at most 3. Hence, it is shown that there is a directed path of length at most 3 between any two vertices of C ∖ C_0. To have a directed path of length at most 3 between any two vertices of C_0, we use the directed 3-cycle (e,x), (x,a_ij), (a_ij,e) for any i, j.□








 

Algorithm: Given a nilpotent group G, it is easy to compute the oriented diameter of Pow(G) with the help of the characterization given in this paper. We can compute the orders of each element in time linear in |G| <cit.>. Once that is done, checking if a group is cyclic is easy. Checking if G has multiple subgroups of prime order p boils down to checking if it has at least p elements of order p. A cyclic group x is maximal if it is not properly contained in y for any y. This can be tested in polynomial time. We note that nilpotency can be tested in polynomial time <cit.>. 




§ NOTES ON ORIENTED DIAMETER OF ENHANCED POWER GRAPHS AND COMMUTING GRAPHS


As a consequence of our results so far, one can easily note the following results regarding the oriented diameter of two related graph classes, namely enhanced power graphs and commuting graphs. First, we provide the definitions of these two graphs.



The enhanced power graph of a group G, denoted by EPow(G), is an undirected graph with vertex set G, in which two vertices x and y are adjacent if and only if they are in a common cyclic subgroup of G, i.e., there exists z in G such that x,y ∈⟨ z ⟩. 




    The commuting graph of a group G, denoted by Com(G), is an undirected graph with vertex set G, in which {x,y} is an edge if xy=yx under the group operation.


From definitions, one can easily note that E(Pow(G)) ⊆ E(EPow(G)) ⊆ E(Com(G)). Hence for a finite group, OD(Com(G)) ≤ OD(EPow(G)) ≤ OD(Pow(G)). Therefore, if OD(Pow(G))≤ d, then d is an immediate upper bound for the oriented diameter of Com(G) and as well as EPow(G). Hence, from <Ref>, we have the following straightforward corollary.


    Let G be a group without any maximal cyclic subgroup of order 2. Then, the oriented diameter of EPow(G) and Com(G) is at most 4.



Moreover, EPow(G) is a complete graph if and only if G is cyclic, and Com(G) is a complete graph if and only if G is abelian. Hence, it makes sense to study oriented diameter for enhanced power graphs of non-cyclic finite groups and commuting graphs for non-abelian finite groups. Now, from our previous discussion, it is clear that <Ref> and <Ref> yield upper bounds for oriented diameter for corresponding enhanced power graphs and commuting graphs. But since there are more edges in EPow(G) and Com(G) than Pow(G), there is a possibility that the actual value of the oriented diameter is less than these upper bounds. Hence, this leads to the following two natural questions.

Question 1: Can we characterize the oriented diameter of enhanced power graphs of non-cyclic finite nilpotent groups?

Question 2: Can we characterize the oriented diameter of commuting graphs of non-abelian finite nilpotent groups?






alpha









§ EXTENDED PRELIMINARY

Let X=(V,E) be a graph. If S ⊆ V(X), then the subgraph with the vertex set S, and edges in E(X) with both endpoints in S, is called the induced subgraph of X on S, and it is denoted by X[S]. In an undirected graph X, a vertex u is said to be a neighbour of a vertex v (and vice versa) if {u,v}∈ E(X). A vertex u is said to be a dominating vertex of a graph X if for any v ∈ V(X), we have {u,v}∈ E(X). The set of all dominating vertices of a graph X is called the set of dominating vertices, denoted by Dom(X). If S,T ⊆ V(X), then E(S,T) denotes the set of edges {s,t}∈ E(X), i.e., the set of edges with one endpoint from S and another endpoint from T. Moreover, we say the edges between S and T are complete edges, if {s,t}∈ E(X) for all s∈ S and for all t∈ T. A bridge in a connected graph is an edge whose removal disconnects the graph.

In an undirected graph X a path between u_1 and u_k is a sequence u_1u_2… u_k of distinct vertices from V(X) such that {u_i,u_i+1}∈ E(X) for each 1≤ i ≤ (k-1). The length of a path is the number of edges participating in it, i.e., the length of the path u_1u_2… u_k is (k-1). A directed path in a directed graph  is defined analogously with the condition (u_i,u_i+1)∈ E() for each 1≤ i ≤ (k-1).

We now state some useful group-theoretic facts. 



    Let x and y be two non-trivial elements of a group G such that xy=yx. Then (xy)^n=x^ny^n.



    Let G be a finite group and x,y ∈ G ∖{e} be two elements such that o(x) and o(y) are co-prime to each other and xy=yx. Then, ⟨ xy ⟩ forms a cyclic subgroup of G of order o(x)· o(y). In particular, o(xy)=o(x)· o(y).


The next property about finite nilpotent groups can be proved from the definition of finite nilpotent groups (see <Ref>). 

<cit.>
    A finite group is nilpotent if and only if two elements with relatively prime orders commute with each other.












































§ APPENDIX





 §.§ Proof of <Ref>





    Since g_1 generates g_2 in G, there exists natural number k_1 ≥ 1 such that g_1^k_1=g_2. Moreover, g_1^k_1+m_1· o(g_1)=g_2, where m_1 is an integer. Since h_1 generates h_2 in H, we can similarly write that h_1^k_2+m_2· o(h_1)=h_2, where k_2≥ 1 is a natural number and m_2 is an integer. The element (g_1,h_1) generates (g_2,h_2) if and only if there is an integer x such that (g_1,h_1)^x=(g_2,h_2), i.e., g_1^X=g_2 and h_1^x=h_2. Such x exists if the congruence equations x≡ k_1 (mod o(g_1)) and x≡ k_2 (mod o(h_1)) have a solution. Now, gcd(|G|,|H|)=1 implies that o(g_1) and o(h_1) are co-prime to each other. So, by the Chinese Remainder Theorem (see <cit.>), the above equations have a solution, say l, and we can write (g_1,h_1)^l=(g_2,h_2). Hence, (g_1,h_1) generates (g_2,h_2) in G× H.










 §.§ An observation for the proof of <Ref>






    Let G be a non-cyclic nilpotent group and |G|=2^mp^n, where p is an odd prime and m,n ≥ 1. If C is a maximal cyclic subgroup of G of order 2p^β, 1≤≤ n, containing a base element x of order 2, then any maximal cyclic subgroup of G containing x is of order 2p^γ, for some γ≥ 1.



    Let y ∈ C be an element of order p^β. Note that xy generates C. For the sake of contradiction, we assume that a maximal cyclic subgroup C' of G containing x has order 2^p^γ where >1, γ≥ 1. Hence, C' must have an element w of order 2^2 (by <Ref>), and w must generate x (because w generates an element of order 2 of C', and x is the only element of order 2 in C'). Now, using <Ref>, w and y commute with each other. Hence, using <Ref> and a well-known number theoretic fact[The congruence equation az≡ b  (mod  n) has a solution for z if and only if gcd(a,n) divides b.], wy generates both y and w. This implies that wy generates both x (since w generates x) and y. Therefore, wy generates xy. So, wy generates C. This contradicts that C is a maximal cyclic subgroup of G.
    






 §.§ Examples of Nilpotent Groups corresponding to <Ref>






 For each of the conditions of <Ref>, we provide examples of finite non-cyclic nilpotent groups that are not in .

    
  * Only condition (a): G=G_1 × G_2 where G_1 is a p-group and G_2 is a q-group, where p and q are odd primes.
    
  * Only condition (b): G= ℤ_4p^n×ℤ_4q^m where p and q are odd primes, and m,n ≥ 1.
    
  * Only condition (c): G= G_1 ×ℤ_p^n where G_1 is a 2-group, p is an odd prime and n ≥ 1.
    
  * Only condition (d): G= Q_8 × G_1 where G_1 is a p-group, and p is an odd prime.
    
  * None of (a)-(d): G= ℤ_2p×ℤ_2p where p is an odd prime.





 §.§ Proof of <Ref> 











 Due to <Ref> and <Ref>, it is sufficient to give an orientation of Pow(G) with diameter 3. Along with the partial orientations _1,_2,_3 given in <Ref>, we also use the following partial orientations:
    
        
        
  _4 : From any base element of order 2, we orient the edges towards all the adjacent non-base elements of order 2p^β (where β≥ 1).
        
        
  _5 : Consider a non-base class N of order 2^ p^, α≥ 2, β≥ 1. By <Ref>, N is adjacent to only one base class M of order 2^2. Then, we orient the edges of E(M,N) as described in _2 of <Ref>. The choices of anchor gadget points of N for M depend on M as stated in <Ref>. In other words, while introducing _5 in a non-base class N of order 2^p^, ≥ 2, ≥ 1, we select a pair of gadget anchor points {n_1,n_2} in N for the base class of order 2^2 adjacent to N in such a way that neither n_1 nor n_2 has used as gadget anchor point in N while introducing _2 for the base class of order p adjacent to N. This is possible since only one base class of odd prime order is adjacent to N and also |N|=ϕ(2^p^)>2^2 = 2·2.

        
  _6 : From any base element of order 2^, ≥ 3, we orient the edges towards all the adjacent non-base elements. Note that these non-base elements are of order 2^δp^β, where δ≥ and β≥ 1.    

        
  _7 : From any non-base element of order 2^2p^β, ≥ 1, we orient the edge towards the (unique) adjacent element of order 2. 
    
 


     We show an illustration of the given orientations in <Ref>. The set B is partitioned into three subsets as follows: (a) R_1: consisting of the elements of order 2; (b) R_2: consisting of the elements of order 2^2 and p; (c) R_3: consisting of the elements of order 2^, ≥ 3, and p^, ≥ 2.
     
   

    
    
     Path directions: First, we point out the following observations, which can be argued similarly to <Ref>:
    
    Note 1:  
    
    There is a directed path of length 2 from any element of order 2^α to any element of order p, using _4 (when α=1) or _5 (when α=2) or _6 (when α≥ 3) along with using _2.

    Note 2: There is a directed path of length 2 from any element of order p^, ≥ 1 to any element of order 2^2 using _2 (when =1) or _3 (when ≥ 2) along with using _5.


    Note 3: There is a directed path of length 2 from any element of order p^, ≥ 1 to any element of order 2 using _2 (when =1) or _3 (when ≥ 2) along with using _7.

Let Γ=Pow(G) and  denote the disjoint union of _1,…,_6. Then,  we use the notation Γ_ to denote the directed graph (V(Γ),). Moreover, let d(a,b) (we use d(a,b) instead of d_Γ_(a,b) as Γ and  are fixed in this context) denote the shortest distance from a vertex a to a vertex b in the directed graph Γ_ and d(a,S)=min_s ∈ Sd(a,s) denote the shortest distance from a vertex a to a set S in Γ_.

Although other than the path direction from a base element to a non-base element, the path directions are the same as those discussed in the proof of <Ref>, we discuss them here also for the sake of completeness.

From <Ref>, one can see that d(v,e)=1 for any non-base element v and d(e,u)=1 for any base element u. This also implies that d(v,u) ≤ 2, i.e., there is a directed path of length at most 2 from any element v∈ NB to any element u∈ B.


We claim that if u ∈ B=R_1∪ R_2∪ R_3 then d(u,NB)=1. For this, observe that if u ∈ R_1, then there exists some v∈ NB such that (u,v) ∈_4. Similarly, if u ∈ R_2, then there exists some v ∈ NB such that (u,v) ∈_2∪_5 and if u ∈ R_3, then there exists some v ∈ NB such that (u,v) ∈_3 ∪_6. 


Noting d(u,NB)=1 for all u∈ B and (v,e)∈_1 for all v∈ NB, we have a directed path of length at most 2 from any element of B to e. Combining such a path with (e,u')∈_1, where u' is any element in B, we get a directed path of length at most 3 between any two elements of B.


 Now, for any non-base element v∈ NB, there exists at least one element u ∈ R_2 such that (u,v)∈_2. Moreover since (e,u)∈_1 for all u∈ R_2 ⊆ B, we have d(e,v)= 2 for all v∈ NB. Now, as (v',e)∈_1 for all v'∈ NB, we get d(v',v)≤ 1+d(e,v) = 3, i.e., there is a directed path of length at most 3 between any two elements in NB. 






Now, the only case that remains to be discussed is when the source vertex u is from B, and the destination vertex v is from NB. Since v is a non-base element, p | o(v), and hence there exists an element a∈⟨ v ⟩ such that o(a)=p. So the base class [a] is in R_2 and participates in a C_4-gadget with the non-base class [v] due to _2 (see <Ref>). Now, if o(u)=2^α, α≥ 1, then using Note 1, we have d(u,a') ≤2 for all a' ∈ [a]. Further using the C_4-gadget between [a] and [v], we have d(u,v) ≤ 3. Else, consider the case when o(u)=p^β, β≥ 1. If 2^2 ∤ o(v), then Note 2 implies d(u,b) ≤ 2, where b is the (unique) element of order 2 in v. Moreover, since b ∈ R_1, we have (b,v) ∈_4. This gives us d(u,v) ≤ 3 in this case. If 2^2 | o(v), then there exists an element c∈v of order 2^2 and [c] participates in a C_4-gadget with [v]. Now, using Note 3, we have d(u,c') ≤ 2 for all c' ∈ [c]. After that, due to the C_4-gadget between [c] and [v] we have d(u,v) ≤ 3.





  §.§.§ Proof of <Ref>










 Due to <Ref> and <Ref>, it is sufficient to give an orientation of Pow(G) with diameter 3. For that, along with the partial orientations _1,_2,_3 discussed in <Ref>, we use the following partial orientation. 



    
        
        
  _4: From any base element of order 2^, ≥ 1, we orient the edges towards all the adjacent non-base elements. Note that these non-base elements are of order 2^δp^β, where δ≥ and β≥ 1.         
    
      

     
    

    
    Path directions: First, we point out the following observations, which can be argued similarly to <Ref>:
    
   Note 1: Using _4 together with _2, there is a directed path of length 2 from any base element of order 2^α, α≥ 1 to any base element of order p. 
    
    Note 2:  Using _3 together with _2, there is a directed path of length 2 from any base element of order p^, ≥ 2 to any base element of order p.
    
Let Γ=Pow(G) and  denote the disjoint union of _1,…,_4. Then, we use the notation Γ_ according to <Ref>. Moreover, let d(a,b) (we use d(a,b) instead of d_Γ_(a,b) as Γ and  are fixed in this context) denote the shortest distance from a vertex a to a vertex b in the directed graph Γ_ and d(a,S)=min_s ∈ Sd(a,s) denote the shortest distance from a vertex a to a set S in Γ_.

Although other than the path direction from a base element to a non-base element, the path directions are the same as those discussed in the proof of <Ref>, we discuss them here also for the sake of completeness.

One can see that d(v,e)=1 for any non-base element v and d(e,u)=1 for any base element u. This also implies that d(v,u) ≤ 2, i.e., there is a directed path of length at most 2 from any element v∈ NB to any element u∈ B.


We claim that if u ∈ B, then d(u,NB)=1. For this, observe that if o(u)=2^, ≥ 1, then there exists some v∈ NB such that (u,v) ∈_4. Similarly, if o(u)= p, then there exists some v ∈ NB such that (u,v) ∈_2 and if o(u)=p^, ≥ 2, then there exists some v ∈ NB such that (u,v) ∈_3. 


Noting d(u,NB)=1 for all u∈ B and (v,e)∈_1 for all v∈ NB, we have a directed path of length at most 2 from any element of B to e. Combining such a path with (e,u')∈_1, where u' is any element in B, we get a directed path of length at most 3 between any two elements of B.


 Now, for any non-base element v∈ NB, there exists at least one element u ∈ B such that o(u)=p and (u,v)∈_2. Moreover since (e,u)∈_1 for all u∈ B, we have d(e,v) = 2 for all v∈ NB. Now, as (v',e)∈_1 for all v'∈ NB, we get d(v',v) ≤ 1+d(e,v) = 3, i.e., there is a directed path of length at most 3 between any two elements in NB. 



Now, the only case that remains to be discussed is when the source vertex u is from B, and the destination vertex v is from NB. At first, observe that since by assumption G has a unique subgroup of order p, it has only one base class [a] of order p. Also, the base class [a] participates in a C_4-gadget with the non-base class [v] due to _2. Now, if o(u)=2^α, α≥ 1, then using Note 1, we have d(u,a')=2 for all a' ∈ [a]. Further using the C_4-gadget between [a] and [v], we have d(u,v) ≤ 3. If o(u)=p^β, β≥ 2, then using Note 2 and the C_4-gadget between [a] and [v], we have d(u,v) ≤ 3. If o(u)=p, it is easy to observe that u ∈ [a]. Now, we use the directed edges between [a] and [v], which are in _2. This gives a directed path from any u ∈ [a] to v ∈ NB of length at most 3 (see <Ref>).






