Protein chainmail variants in dsDNA viruses

1.   Introduction

In fields such as data structures, computer algorithms, data encryption, security, and networking, computer science relies heavily on graph theory. For instance, designs of a database, routing problems, and networking based on the key ideas of graph theory, namely cycles and trees. Many computer security algorithms and ciphers are similarly based on modular arithmetic from number theory. In these areas, a strong mathematical background and a clear understanding of modular arithmetic, graph theory and algorithms needs to be developed to enjoy the subject. Computer software or a program without adequate knowledge of mathematics is often difficult to understand. The entire structure of an algorithm can be understood through a flow chart or its graph (or digraph). Graphs (or digraphs) are thus much more useful for a better understanding of structurally dependent algorithms and/or outputs. Digraphs based on congruence equations are a primary interest in the field of discrete mathematics for number theorists and computer scientists. Power digraphs have a broad range of applications that are easily recognizable in almost every field and presented with the basic properties of integers. For instance, if a typical power digraph is described and its loops are discovered. Then, instead of ordinary integers, one can consider these vertices (that is, loops) in forming a new cipher. Obviously, it would be difficult to decode this type of cipher unless one knows the correct mapping and its reverse mapping (if possible). In fact, a typical corresponding congruence must be solved to decode such a produced cipher. The problem of factorization in computer science is a very difficult problem for large integers. For such an integer, a digraph which assigns a component to its divisor can always be described. The divisor number can therefore be enumerated as the number of components that are non-isomorphic. The required integer may therefore be written canonically. Let's define our power digraph before proceeding further.

Let $ m > 0 $ be any integer and $ \overline{r} $ denotes the set of all integers which leave remainder $ r $ under modulo $ m $, also referred as a residue class of $ m $. Thus, $ \{\overline{0}, \; \overline{1}, \; \overline{2}, \; \overline{3}, \; \dotso, \; \overline{m-1}\} $ is the set of all residue classes of $ m $. This set is called a complete residue system (CRS). We construct a digraph $ G(p, m) $ on this set of complete residue classes of $ m $ and build a directed edge from $ u $ to $ v $ if and only if $ u^{p} \equiv \; v\; (\text{mod}\; m) $. The vertices $ u_{1}, u_{2}, ..., u_{s} $ will form a cycle of length $ s $ if

The indegree of a vertex $ a $ is the count of edges incident with it and the number of edges leaving from a vertex $ a $ is called outdegree of $ a. $ The indegree and outdegree are labeled as $ indeg(a) $ and $ outdeg(a) $, respectively. The cycles of length one are called fixed points of the map $ f(u) = u^{p} $ and cycles of length $ q $ are called $ q $-cycles. A maximal connected simple subetaaph of the corresponding digraph $ G(p, m) $ is termed as a component. Since every integer lies in a unique residue class of $ m $, so its outdegree must be one.

If indegrees and outdegrees of all vertices are the same then the corresponding digraph is called a regular digraph. In this case, a digraph is regular if the indegree of every vertex is one (since the outdegree of each vertex is already one). If the indegrees of all vertices are either a positive integer $ d $ or $ 0 $, we then call it a semiregular digraph. Let $ G_{1}(p, m) $ and $ G_{2}(p, m) $ denote the subdigraphs induced by the proposed digraph $ G(p, m) $ over the set of vertices which are either coprime to $ m $ or not, respectively. Note that the digraphs $ G_{1}(p, m) $ and $ G_{2}(p, m) $ are disjoint and their union is $ G(p, m) $. The digraph $ G(11, 17) $ is depicted in Figure 1.

Figure 1.  The digraph $G (11, 17)$.

DownLoad: Full-Size Img PowerPoint

Power digraphs have been of great interest for the last few decades. In 1967, Bryant ^[1] employed quadratic digraphs and enumerated isomorphic subetaoups of a finite group. Szalay ^[2] investigated some interesting properties of power digraphs based on congruences and established the existence of cycles in components. In 1996, Rogers ^[3] and Somer et al. ^[4] investigated the structures of quadratic maps and explored a few results on fixed points, existence of cycles and few decomposition of components. Mahmood and Ahmad ^[5] established many results for $ k $-array digraphs and completely described an enumeration of squares of $ 2^k $ using modular arithmetic for any intger $ k $. Aslam and Mahmood introduced and investigated simple graphs over exponential congruences and characterized all cycles and components completely in ^[6]. Yangjiang et al. ^[7] and Somer et al. ^[8] introduced and investigated the symmetric structures (isomorphic components) of such digraphs. For a fixed $ k $, many useful results on loops, cycles, components and symmetry of power digraphs for the congruence equation $ x^{k}\equiv y \; (\text{mod} \; m) $ have been proposed and proved in ^{[9,10,11,12,13]}. Akbari ^[14] established a relation between edge chromatic number of $ G(R) $ with the maximum degree of $ G(R) $, where $ G(R) $ denotes the zero-divisor graph over of a finite commutative ring $ R. $ Wei et al. and Rezaei et al. ^[15,16,17] discussed graphs based on quadratic and cubic congruences over finite integral rings. Carlip and Mincheva ^[18] defined an $ M $-ordered symmetric digraph of $ G $ based on $ M $-size subsets, each containing $ M $-isomorphic components. Deng and Yuan ^[19] investigated symmetric digraphs for a fixed power modulo $ n $. Meemark and Wiroonsri ^[20,21] discussed the structure of $ G(R, k) $, where $ R $ is the quotient ring of polynomials over finite fields and $ k $ is the modulus. Mahmood and Ali ^[22,23,29] investigated new numbers on euler totient, super euler function and labeling algorithm on several classes of graphs with application. Alolaiyan et al. ^[24] studied non-conjugate graphs associated with finite groups. Portilla et al. ^[25] generalize the classical definition of Gromov hyperbolicity to the context of directed graphs. It is worth mentioning that the problem of enumeration of components of power digraphs is still open. In fact, previously all structures have been established for a fixed power $ k $. In this piece of work, we generalize the structures of these digraphs when power is an odd prime $ p $. That is, we incorporate the congruence, $ x^{k}\equiv y \; (\text{mod} \; m) $.

We organize our paper as follows. In Section 1, we introduce our digraph with some important definitions and also provide some new results on fixed points. In Section 2, we prove some results that enumerate cyclic vertices as well as the existence of a $ t $-cycle in $ G(p, m) $. Then, we define two subdigraphs $ G_{1}(p, m) $ and $ G_{2}(p, m). $ Then after, we elaborate cyclic structures and enumerate components of these subdigraphs for $ m = 2^{r} $ and $ m = p^{r} $ for all positive integers $ r. $ Finally, we prove that the digraph $ G_{1} (p, m) $ consists of $ p-1 $ isomorphic trees where as $ G _{2}(p, m) $ is a tree with root at 0 with indeg$ (0) = p^{k-\lceil\frac{k}{p}\rceil} $. In Section 3, we characterize regularity and semiregularity of $ G_{1}(p, m) $. We need the following definitions for use in sequel.

Definition 1.1. ^[26] Euler totient function counts the positive integers up to a given integer $ m $ that are relatively prime to $ m $. It is written using the Greek letter phi as $ \phi(m) $, also called Euler phi function.

Definition 1.2. ^[26] Let $ m > 0 $ be any integer. For a prime $ p $, the Carmichael $ \lambda $-function (or $ \lambda(m) $) is defined as follows: $ \lambda(1) = 1 = \phi(1), \; \lambda(2) = 1 = \phi(2), \; \lambda(4) = 2 = \phi(4), \; \lambda(2^k) = \frac{1}{2}\; \phi(2^k), \; k \; \geq 3 $, and $ \; \lambda(p^k) = \phi(p^k), \; k\; \geq 1. $

Theorem 1.3. ^[27] (Carmichael). Let $ a, m \in\mathbb{N} $. Then $ a^{\lambda(m)} \equiv 1\; ({\rm mod}\; m) $ if and only if $ gcd(a, m) = 1 $. Here, $ gcd(a, m) $ is the greatest common divisor of $ a $ and $ m $.

Theorem 1.4. The Chinese Remainder Theorem (for detail see page 230, Fact 4 of ^[28])

Define

and

If $ gcd(2^{b}, u) = 1, $ then the number of solutions for the congruence $ u^{t}\equiv a\; ({\rm mod}\; 2^{b}) $ is either $ 0 $ or $ (gcd(2, t))^{\eta_{1}}(gcd(2^{b-2}, t))^{\eta_{2}} $.

The following inequality can easily be proved using mathematical induction.

Lemma 1.5. For $ t\geq2, \; t\leq \beta (t-1), \; \beta = 2, \; 3, \; 4, \dotso. $

Lemma 1.6. For a prime $ p $ of the type $ p\; \equiv\; 3 \; ({\rm mod}\; 4), \; k\geq 4, $ then, $ 1, \; 2^{k-1}\pm\; 1, \; 2^{k}-1 $ are fixed points in $ G_{1}(p, \; 2^{k}) $ and $ 0 $ is the only fixed point in $ G_{2}(p, \; 2^{k}) $.

Proof. For $ k\geq 4, \; \alpha = 1+2^{k-1} $ is a fixed point if $ \alpha^{p}\equiv \alpha \; (\text{mod}\; 2^k). $ For this, note that

As $ k\geq4 $, Lemma 1.5 invokes, $ \; k\leq \beta (k-1), \; \beta = 2, \; 3, \; 4, \dotso, \; n $ which further gives $ 2^{k} |2^{\beta(k-1)}. $ But then,

Also, $ p = 4t+3 $ for some integer $ t = 0, \; 1, \; 2, \dotso $. Using the expression of $ p $ together with Eqs (1.2) and (1.3), we get

Similarly, we can follow the same procedure to prove the remaining fixed points. Also by Theorem 1.4, the number of solutions of $ u^{p-1}\equiv 1\; (\text{mod}\; 2^{b})\; \text {with}\; 2\nmid u $ is $ (gcd(2, p-1))^{\eta_{1}}(gcd(2^{b-2}, p-1))^{\eta_{2}}. $ Note that, in our case, $ {\eta_{1}} = {\eta_{2}} = 1, \; \text {with}\; b\geq3 $. As $ p\equiv 3\; (\text{mod}\; 4) $ can also be written as $ p-1 = 2(1+2t), \; t\in \mathbb{Z}^{+} $. Hence, we get $ gcd(2, 2(1+2t))\cdot gcd(2^{b-2}, 2(1+2t)) = 2\cdot2 = 4 $. This shows that there are exactly four fixed points.

Proposition 1.7. The graph $ G_{1}(p, 2^k) $ has $ 8 $ fixed points which are $ 1, \; \pm\; 1+2^{k-1}, \; \pm\; 1+2^{k-2}, \; 2^{k-1}, \\-(2^{k-2}\pm\; 1)+2^{k} $ and $ G_{2}(p, 2^k) $ contains only $ 0 $ as a fixed point where $ k\geq4 $ and $ p\; \equiv\; 5 \; ({\rm mod}\; 8). $

Proof. For $ k\geq 4, \; \alpha = 1+2^{k-2} $ is fixed point if $ \alpha^{p}\equiv \alpha \; (\text{mod}\; 2^k). $ For this, note that

As $ k\geq4 $, Lemma 1.5 invokes, $ k\geq4, \; k\leq \beta (k-2), \; \beta = 2, \; 3, \; 4, \dotso, n $. Then $ 2^{k} |2^{\beta(k-2)}. $ Hence

Also, $ p = 8t+5 $ for some integer $ t = 0, \; 1, \; 2, \dotso. $ Using $ p $ together with Eq (1.5) in (1.4), we get

The remaining fixed points can be proved in a similarly technique. Also by Theorem 1.4, the number of solutions of $ u^{p-1}\equiv 1\; (\text{mod}\; 2^{b})\; \text {with}\; 2\nmid u $ is $ (gcd(2, p-1))^{\eta_{1}}\cdot (gcd(2^{b-2}, p-1))^{\eta_{2}}. $ In our case, take $ {\eta_{1}} = {\eta_{2}} = 1, \; \text {with}\; b\geq 4 $. As $ p\equiv 5\; (\text{mod}\; 8) $ implies that $ p-1 = 4(1+2t), \; t\in \mathbb{Z}^{+} $. Hence, we get $ gcd(2, 4(1+2t))\cdot gcd(2^{b-2}, 4(1+2t)) = 2\cdot4 = 8 $. This shows that there are exactly eight fixed points.

Figure 2 reflects Proposition 1.7.

Figure 2.  The digraph $G (29, 2^5)$.

DownLoad: Full-Size Img PowerPoint

2.   Enumeration of cyclic vertices and components

The vertices $ v_{1}, v_{2}, v_{3}, \dotso, v_{t} $ compose a component if for every $ j, 1\leq j\leq t $, there exists some $ i, \; 1\leq i\leq t $, such that $ v^{p}_{j}\equiv v^{p}_{i}\; (\text{mod}\; m), $ for all $ j\neq i $. By ^[8], it has been established that there exists one and only one cycle in every component of such digraphs. While the enumeration of components is still an open problem. In this section, an enumeration of cycles and components (up to isomorphism) of $ G(p, 2^k) $ is proposed for certain classes of $ p $. Also, we examine all integers for which there are $ p $ number of components. The following theorem also validates a similar result given in ^[4] for a quadratic congruences.

Theorem 2.1. For an odd prime $ p $, define $ m = 2^{i}p^{t}, \; i = 0, \; 1, \; 2, \; t\geq1. $ Then $ G(p, m) $ contains an $ s $-cycle if and only if $ p^{s}\equiv 1\; ({\rm mod}\; d) $ for a smallest integer $ s > 0 $ provided $ d > 0 $ with $ d \mid \lambda(m). $

Proof. Let $ m = 2^{i}p^{t}, \; i = 0, \; 1, \; 2, \; t\geq1 $ and suppose $ G(p, m) $ contains an $ s $-cycle. Assume that $ u $ is an arbitrary vertex on this cycle. Then $ u^{p^{s}}\equiv u\; (\text{mod} \; 2^{i}p^{t}) $ for a smallest integer $ s > 0 $. That is, $ u(u^{p^{s}-1}-1) \equiv 0\; (\text{mod} \; \; 2^{i}p^{t}). $ Clearly, $ gcd(u, u^{p^{s}-1}-1) = 1 $. Thus if we let $ m_{1} = gcd(u, m) $ and $ m_{2} = m / m_{1} $, then $ s > 0 $ must be smallest such that $ u \equiv 0 \; (\text{mod} \; m_{1}) $ and $ v^{p^{s}-1}\equiv 1\; (\text{mod} \; m_{2}) $. Using Chinese Reminder Theorem, we get a solution $ x $ to satisfying $ x\equiv 1 \; (\text{mod} \; m_{1}) $ and $ x\equiv a \; (\text{mod} \; m_{2}). $ Consequently, the integer $ s > 0 $ is, in fact, least such that $ x^{p^{s}-1}\equiv 1 \; (\text{mod} \; m_{1}) $ and $ x^{p^{s}-1}\equiv 1\; (\text{mod} \; m_{2}). $ Both yields that, $ x^{p^{s}-1}\equiv 1\; (\text{mod} \; 2^{i}p^{t}). $ Let $ d = ord_{m}^{x} \; (d = ord^{x}_{m} $ if $ d $ is the least positive integer such that $ x^d \equiv 1 \; (\text{mod}\; m) $). Then, $ x\equiv 1 \; (\text{mod} \; m_{1}) $ enforces that $ s > 0 $ is the least integer such that $ p^{s}\equiv1 \; (\text{mod} \; d). $ Also, if $ d = ord_{m}^{x} $, then $ (x, 2^{i}p^{t}) = 1 $, so by Carmichael Theorem, it is evident that $ d\; |\; \lambda(2^{i}p^{t}). $

Conversely, suppose $ d > 0 $ with $ d\; |\; \lambda(m) $ and let $ u = g^{\lambda(2^{i}p^{t})\; |\; d} $. Then $ d = ord_{m}^{u} $. As $ d\; |\; p^{s}-1 $ but $ d \nmid p^{l}-1 $ for $ 0 \leq l < s $. We deduce that the integer $ s > 0 $ is least so that $ u^{p^{s}-1}\equiv 1\; (\text{mod}\; 2^{i}p^{t}) $. Equivalently, $ u\cdot u^{p^{s}-1}\equiv u^{p^{s}}\equiv u\; (\text{mod} \; 2^{i}p^{t}). $

Theorem 2.2. For any prime $ p $ with $ p \equiv 3 \; ({\rm mod}\; 8) $, the vertices $ 1+p^{s}2^{k-2}, k\geq4 $ for $ s = 0, \; 1 $ form a cycle of length 2 in $ G(p, 2^{k}). $

Proof. The vertices $ \alpha_{0} $ and $ \alpha_{1} $ form a cycle of length 2 in $ G(p, 2^{k}) $ if and only if $ \alpha_{0}^{p} \equiv\alpha_{1}\; \; (\text{mod}\; 2^{k}), \; \alpha_{1}^{p} \equiv\alpha_{0}\; \; (\text{mod}\; 2^{k}) $. Now

As $ k\geq4 $, Lemma 1.5 invokes, $ k\geq4, \; k\leq \beta (k-2), \; \beta = 2, \; 3, \; 4, \dotso, n $. That is, $ 2^{k}\; |\; 2^{\beta(k-2)}. $ Therefore,

$ \; s = 0, \; 1 $ and $ p\; \equiv\; 3 \; (\text{mod}\; 8). $ Also, $ p = 8t+3 $ for some integer $ t = 0, \; 1, \; 2, \dotso $. Using this together with Eq (2.3), for $ s = 1 $ we get that

From Eqs (2.3) and (2.4), we find that the vertices $ 1+p^{s}2^{k-2} $ for $ s = 0, \; 1 $ form a cycle of length 2 in $ G(p, \; 2^{k}) $, where $ k\geq 4 $ and $ p\; \equiv\; 3 \; (\text{mod}\; 8). $

Theorem 2.3. For any prime $ p $ such that $ p\equiv 3 \; ({\rm mod}\; 8) $, the vertices $ 2^{k}+p^{p^{s}}, \; k > 2 $ for $ s = 0, \; 1, \; 2, \; 3, \dotso, \; 2^{k-2}-1 $ form a cycle of length $ 2^{k-2} $ in $ G(p, \; 2^{k}). $

Proof. The vertices $ \alpha_{0}, \; \alpha_{1}, \; \alpha_{2}, \dotso, \; \alpha_{2^{(k-2)}-1} $ form a cycle of length $ 2^{k-2} $ in $ G(p, \; 2^{k}) $ if and only if $ \alpha_{0}^{p} \equiv\alpha_{1}\; \; (\text{mod}\; 2^{k}), \; \alpha_{1}^{p} \equiv\alpha_{2}\; \; (\text{mod}\; 2^{k}), \dotso, \; \alpha_{2^{(k-2)}-1}^{p} \equiv\alpha_{0} \; \; (\text{mod}\; 2^{k}). $ Now

Since $ k > 2, \; k\leq \beta (k), \; \beta = 1, 2, \; 3, \; 4, \dotso, n $. Then $ 2^{k} |2^{\beta(k)}. $ Hence,

putting in Eq (2.5), we get

$ s = 0, \; 1, \; 2, \; 3, \dotso, 2^{(k-2)}-1 $ and $ p\; \equiv\; 3 \; (\text{mod}\; 8). $ Finally, we noted that

Since, $ p^{2^{(k-2)}-1}\; \equiv\; 1 \; (\text{mod}\; 2^{k}) $, for any $ k > 2 $ it implies that,

Eqs (2.7) and (2.8) give that vertices $ 2^{k}+p^{p^{s}}, k > 2 $ for $ s = 0, \; 1, \; 2, \; 3, \dotso, 2^{(k-2)}-1 $ form a cycle of length $ 2^{k-2} $ in the graph $ G(p, \; 2^{k}) $, where $ p\; \equiv\; 3 \; (\text{mod}\; 8). $

Theorem 2.4. For any prime $ p $ such that $ p\equiv3 \; ({\rm mod}\; 8), $ the vertices $ 2^{k}+(p+2)^{p^{s}}, k > 2 $ for $ s = 0, \; 1, \; 2, \; 3, \dotso, 2^{k-2}-1 $ form a cycle of length $ 2^{k-2} $ in the graph $ G(p, \; 2^{k}). $

The proof is on similar lines as illustrated in the proof of Theorem 2.3.

The following result is a simple consequence of last two theorems.

Corollary 2.5. For any prime $ p $ such that $ p\equiv 3 \; ({\rm mod}\; 8), $ the graph $ G(p, \; 2^{k}) $ has cycle of length $ 2^{k-(r+2)} $, where $ k > 2, \; 0\leq r\leq k-3 $.

In the following theorem, we find all integers for which there are $ p $ components.

Theorem 2.6. (1) The number of components of $ G(p, m) $ is $ p $ if $ m = \; p^{k} $ for some positive integer $ k $ and $ p $ is an odd prime.

(2)The number of components of $ G(p, m) $ is $ p $ if $ m $ is prime of the form $ m = (p-1)\times p^{k}+1 $ for some positive integer $ k, $ where $ p\equiv 3 \; ({\rm mod}\; 4) $.

Proof. (1) If $ m = p^{k} $ then by [^[8], Theorem 6.6 on page 2005], we have exactly $ p $ fixed points. Now these are either isolated or the roots of their respective components. Thus, if $ m $ is any number for which we have more than $ p $ components then there must be a cycle of length $ s > 1. $ But then by Theorem 2.1, $ s $ is the least positive integer such that $ p^{s}\equiv 1 \; (\text{mod} \; d) $, where $ d \mid \lambda(p^{k}) $ and $ d > 0. $ That is, $ d \mid p^{s}-1 $ and $ d \mid \lambda(m) = (p-1)\times p^{k} $ as well. This clearly enforces that $ d = p-1. $ But then $ p^{k}\equiv 1 \; (\text{mod} \; p-1) $ for each value of $ k. $ In particular, if $ 1\leq r < s, $ then $ p^{r}\equiv 1 \; (\text{mod} \; p-1) $ as well. This has certainly provided a contradiction against the minimality of $ s. $ Thus, this case is not all possible. Consequently, $ G(p, m) $ has $ p $ components.

(2) If $ m $ is prime of the form $ m = (p-1)\times p^{k}+1 $ for some positive integer $ k, $ where $ p\equiv 3 \; (\text{mod}\; 4) $. Then it can easily be seen that there are $ p $ fixed points by [^[8], see Theorem 6.6 on page 2005] and by similar argument as part 1 there does not exist cycle of length greater than $ 1 $. Thus, there are exactly $ p $ components.

If $ d $ is the least positive integer such that $ n^d \equiv 1 \; (\text{mod}\; m) $ then $ d $ will be termed as order of $ n $ modulo $ m $, it is denoted as $ d = ord^{n}_{m} $. In the following result, we show that the digraph $ G_{1}(p, 2^{k}), \; k > 0 $ contains only the cycles of lengths which are the powers of $ 2 $ (excluding fixed points) and $ G_{2}(p, 2^{k}) $ form a tree with root $ 0 $.

Theorem 2.7. For any positive integer $ k $, the digraph $ G_{1}(p, 2^{k}), $ contains cycles of lengths as integral powers of 2. That is, the length of any cycle in $ G_{1}(p, 2^{k}) $ must be of the form $ 2^t, \; t\in \mathbb{Z^{+}} $ and $ t < k $ (excluding fixed points) while $ G_{2}(p, 2^{k}) $ form a tree with root $ 0 $. Moreover, $ \mathit{\text{indeg}} (0) = 2^{k-\lceil\frac{k}{p}\rceil}. $

Proof. It is well known that there must be an equal number of residues of $ m = 2^{k} $ which are prime to $ m $ and those which are not prime to $ m. $ Thus the digraphs $ G_{1}(p, m) $ and $ G_{2}(p, m) $ contains equal number of vertices $ 2^{k-1}, $ by Lemma 1.6. It can be seen that, $ \; \pm\; 1+2^{k-1}, \; -1+2^{k}, \; 1, $ are the only fixed points of $ G_{1}(p, \; 2^{k}p) $, where $ p\; \equiv\; 3 \; (\text{mod}\; 4), $ and by Proposition 1.7. $ G_{1}(p, 2^k) $ has $ 8 $ fixed points which are $ 1, 2^{k-1}\pm1, \; \pm1+2^{k-2}, \; 2^{k-1}, \; -(2^{k-2}\pm\; 1)+2^{k} $, where $ p\; \equiv\; 5 \; (\text{mod}\; 8), $ and if $ p = 2^ua+1 $ ($ p\equiv 1 \bmod8 $) with an odd $ a $, then $ G_1(p, 2^k) $ contains $ 2^{u+1} $ fixed points, the elements of order dividing $ 2^u $, provided that $ k\ge u+2 $. By Theorem 2.1, there would be a cycle of length $ s $ if and only if $ s = ord^{p}_{d} $, for some divisor $ d $ of $ \lambda (m) = 2^{k-2}. $ Now if there exists such a cycle, then $ s $ being order of $ p $ modulo a divisor of $ 2^{k-1} $ must be of the form $ 2^t, $ for some integer $ t > 0. $ As far the other case is concerned, we note that all, even residues of $ 2^k, $ will be connected by a tree. Thus, $ (2^{k-\lceil\frac{k}{p}\rceil}) $ numbers, namely $ 2^{\lceil\frac{k}{p}\rceil}, \; 2\cdot2^{\lceil\frac{k}{p}\rceil}, \; 3\cdot2^{\lceil\frac{k}{p}\rceil}, \; \dotso, 2^{k-\lceil\frac{k}{p}\rceil}\cdot2^{\lceil\frac{k}{p}\rceil} $ are mapped onto $ 0 $. Consequently, $ indeg (0) = (2^{k-\lceil\frac{k}{p}\rceil}). $

In the following theorem, we investigate the structure of isomorphic trees.

Theorem 2.8. Let $ t $ be any positive integer and $ m = p^{t}. $ Then the digraph $ G _{1} (p, \; m) $ consists of $ p-1 $ isomorphic trees. Moreover, $ G _{2} (p, \; m) $ is a tree with root at $ 0 $ and indeg$ (0) = p^{t-\lceil\frac{t}{p}\rceil}. $

Proof. We know that the digraph $ G (p, \; m) $ has exactly $ p $ components with $ p $ fixed points (For detail, see Theorem 6.6 on page 205 in ^[8]). Note that $ p^{t-\lceil\frac{t}{p}\rceil} $ elements, namely, $ p^{\lceil\frac{t}{p}\rceil}, 2\cdot p^{t-\lceil\frac{t}{p}\rceil}, 3\cdot p^{t-\lceil\frac{t}{p}\rceil}, \dotso, \\p^{t-\lceil\frac{t}{p}\rceil}\cdot p^{\lceil\frac{t}{p}\rceil} $ are adjacent to 0 in $ G_{2} (p, \; m). $ Also, $ p|\phi(m) = (p-1)\cdot p^{t-1} $, by Theorem 3.3, we obtain that the digraph $ G_{1} (p, \; m) $ is semiregular and every vertex, either has degree $ 0 \; \text{or}\; p $. It is clear that this digraph has a tree with root $ 0 $. Now assume the set of non-zero fixed points as $ \{1, \; a_{2}, \; a_{3}, \dotso, a_{\frac{p-1}{2}}, \; m-1, \; m-a_{2}, \; m-a_{3}, \dotso, m-a_{\frac{p-1}{2}} \}. $ Define $ T_{1}, \; T_{m-1}, \; T_{a_{2}}, \; T_{m-a_{2}} $ so on $ \; T_{a_{\frac{p-1}{2}}} $ and $ T_{m-a_{\frac{p-1}{2}}} $ trees containing the fixed points $ \{1, \; m-1, \; a_{2}, \; m-a_{2}, \; a_{3}, \; m-a_{3}, \dotso, \; a_{\frac{p-1}{2}}, \; m-a_{\frac{p-1}{2}} \} $, respectively. we can easily deduce that $ T_{1}\cong T_{m-1} $, $ T_{a_{2}}\cong T_{m-a_{2}}, \dotso, \; T_{a_{\frac{p-1}{2}}}\cong T_{m-a_{\frac{p-1}{2}}}. $ Now, if we multiply each vertex of the tree $ T_{1} $ by number $ a_{2} $, we have tree $ T_{a_{2}}. $ Similarly, if we multiply each vertex of the tree $ T_{1} $ by number $ a_{3} $, we have a tree $ T_{a_{3}}. $ By continuing this fashion if we multiply $ T_{1} $ by $ {a_{\frac{p-1}{2}}} $ have a tree $ T_{a_{\frac{p-1}{2}}} $. This is possible if $ gcd(a_{i}, m) = 1, $ where $ i = 1, 2, 3, \dotso, a_{\frac{p-1}{2}}. $ Consequently, it yields that, $ T_{1}\cong T_{{a_{2}}}, \; T_{1}\cong T_{{a_{3}}}, \dotso, T_{1}\cong T_{ {a_{\frac{p-1}{2}}}}. $

Figures 3 and 4 reflect Theorem 2.7 and Theorem 2.8, respectively.

Figure 3.  The digraph $G (11, 2^{6})$.

DownLoad: Full-Size Img PowerPoint

Figure 4.  The digraph $G (11, 11^{2})$.

DownLoad: Full-Size Img PowerPoint

Now, we discuss the components of the digraph $ G(p, \; m) $. The notation $ A_{t}(G(p, \; m)) $ denotes the number of cycles of length $ t $ in the digraph $ G(p, m). $

Theorem 2.9. For any prime $ p $ such that $ p\equiv 3 \; ({\rm mod}\; 8), $ the graph $ G(p, \; 2^{k}) $ has $ 11+4(k-5) $ components, where $ k > 4. $

Proof. To prove this result, first we find the number of cycles of length $ 2^{k-(r+4)} $, where $ k > 4, \; 0\leq r\leq k-5 $ and $ p\equiv 3 \; (\text{mod}\; 8). $ By Lemma 1.5, it is found that $ A_{1}(G(p, \; 2^{k})) = 5 $ and obtained the number of cycles of length two $ A_{2}(G(p, \; 2^{k})) $ by using Theorem 6.6 of ^[8] for $ \delta_{i} = 2 $, given as

Now $ gcd(\lambda(2^{k}), p^{2}-1) = 8 $, where $ p\equiv 3 \; (\text{mod}\; 8), \; k > 4 $ and $ A_{1}(p, \; 2^{k}) = 5 $, hence, $ A_{2}(G(2^k, p)) = 6 $

$ gcd(\lambda(2^{k}), p^{2^2}-1) = 2^4 = 16, \; p\equiv 3 \; (\text{mod}\; 8), \; k > 4 $, $ A_{1}(p, \; 2^{k}) = 5 $ and $ A_{2}(p, \; 2^{k}) = 6. $

$ gcd(\lambda(2^{k}), p^{2^3}-1) = 2^5 = 32, \; p\equiv 3 \; (\text{mod}\; 8), \; k > 4 $, $ A_{1}(p, \; 2^{k}) = 5 $, $ A_{2}(p, \; 2^{k}) = 6 $, and $ A_{3}(p, \; 2^{k}) = 4 $.

$ gcd(\lambda(2^{k}), p^{2^{k-4}}-1) = 2^{k-2}, \; p\equiv 3 \; (\text{mod}\; 8), \; k > 4 $, $ A_{1}(p, \; 2^{k}) = 5 $, $ A_{2}(p, \; 2^{k}) = 6, \; A_{2^2}(p, \; 2^{k}) = \; A_{2^3}(p, \; 2^{k}) = \dotso = A_{2^{k-4}}\; (p, \; 2^{k}) = 4. $

So by counting principle adding $ A_{1}(p, \; 2^{k}) = 5 $, $ A_{2}(p, \; 2^{k}) = 6, \; A_{2^2}(p, \; 2^{k}) = \; A_{2^3}(p, \; 2^{k}), \; \dotso, A_{2^{k-4}}(2^k, p) = 4 $. We get $ 11+4(k-5) $ components, for $ k > 4, $ and $ p\equiv 3 \; (\text{mod}\; 8). $

Theorem 2.10. For any prime $ p $ such that $ p\equiv 5 \; ({\rm mod}\; 8), $ the graph $ G(p, \; 2^{k}) $ has $ 13+4(k-5) $ components, where $ k > 4. $

The proof is on similar lines as illustrated in the proof of Theorem 2.9.

Theorem 2.11. Let $ p $ be any prime such that $ p\equiv 7 \; ({\rm mod}\; 2^4). $ Then graph $ G(p, \; 2^{k}) $ has $ 19+8(k-6) $ components, where $ k > 5. $

The proof is on similar lines as illustrated in the proof of Theorem 2.9.

Figure 5(a) and (b) reflect Theorem 2.9.

Figure 5.  The digraph $G (19, 2^{7})$.

DownLoad: Full-Size Img PowerPoint

3.   Regularity and semiregularity

In this section, we give conditions for the regularity and semiregularity of our proposed graph. In the following result, we characterize the regularity of the digraph $ G_{1}(p, m). $

Lemma 3.1. The digraph $ G_{1}(p, m) $ is regular if and only if $ p \nmid\phi (m), $ where $ \phi $ is the Euler's function.

Proof. We suppose that $ G_{1}(p, m) $ is regular. The regularity of $ G_{1}(p, m) $ yields that the indeg$ (v) = 1 $ for every vertex $ v $ in $ G_{1}(p, m). $ This means that $ x^{p}\equiv v \; (\text{mod} \; m) $ has a unique solution. Without loss of generality, assume $ v \equiv 1 \; (\text{mod} \; m) $ and let $ \beta $ be the unique solution of the congruence $ x^{p}\equiv 1 \; (\text{mod} \; m). $ That is, $ \beta^{p}\equiv 1 \; (\text{mod} \; m). $ Now, if $ p \mid \phi(m) $ then $ \phi(m) = p\cdot t $ for some integer $ t $. Note that, $ t = 1 $ is impossible as $ \phi(m) $ is always even. Also by Euler Theorem, $ \beta^{\phi(m)}\equiv1\; (\text{mod} \; m) $ as $ (\beta, \; m) = 1 $ (by definition of $ G_{1}(m) $). Then, $ \beta^{p\cdot t}\equiv1\; (\text{mod} \; m) $ or $ (\beta^{t})^{p}\equiv1\; (\text{mod} \; m) $. This shows that $ \beta^{t}, \; t > 1 $ is another solution of $ x^{p}\equiv1 \; (\text{mod} \; m). $ This means that $ indeg(1) = 2 $, a contradiction against the fact that $ G_{1}(p, m) $ was regular. Therefore, $ p \nmid \phi(m) $. Conversely, let $ p \nmid \phi (m) $ and we suppose that $ G_{1}(p, m) $ is not regular. Then there must be at least one vertex $ \alpha $ such that $ indeg(\alpha) > 1. $ For the sake of convenience, take $ \alpha = 1 $ with $ indeg(\alpha) = 2. $ This means that $ x^{p}\equiv1 \; (\text{mod} \; m) $ has two solutions. Let these be $ \alpha $ and $ \alpha^{t}, \; t > 1. $ Then, $ \alpha^{p}\equiv1\; (\text{mod} \; m) $ and $ \alpha^{p't}\equiv1\; (\text{mod} \; m) $. But, $ \alpha^{\phi(m)}\equiv1\; (\text{mod} \; m). $ Hence, we deduce that either $ \phi (m) = p $ or $ \phi (m) = p\cdot t. $ As $ \phi(m) $ is always even, so $ \phi(m) = p\cdot t. $ That is, $ p\mid \phi(m), $ a contradiction.

Lemma 3.2. Let $ m > 0 $ be any square free integer and $ p $ be any odd prime. The digraph $ G(p, m) $ is cyclic if and only if $ p \nmid\phi (m). $

Proof. Recall that a digraph is cyclic if all of its components are cycles. Also, every regular digraph is cyclic. Hence, by Lemma 3.1, $ G_{1}(p, \; m) $ is cyclic if and only if $ p \nmid\phi (m). $ For $ G_{2}(p, \; m), $ suppose $ p \nmid \phi (m) $ and let $ \alpha $ be any vertex in $ G_{2}(p, \; m) $. Let $ p^{'} $ be an odd prime such that $ p^{'}\mid gcd (\alpha, m). $ Then we can find integers $ r $ and $ s $ such that $ \alpha = rp^{'} $ and $ m = p^{'}s $ with $ gcd (r, s) = 1 $. Now if $ \beta $ is the solution of the congruence $ x^{p}\equiv \alpha\; (\text{mod} \; m), $ then $ \beta^{p}\equiv \alpha\; (\text{mod} \; m) $ yields that $ \beta^{p} = \alpha + m t $ for some integer $ t $. But then $ \beta^{p} = rp^{'} + sp^{'}t. $ Consequently, $ p^{'} \mid \beta $ such that $ p^{'} \mid gcd (\alpha, m). $ This means that $ \beta^{p}\equiv \alpha\; \equiv 0\; (\text{mod} \; p^{'}). $ Thus we conclude that a number $ \beta $ exists such that it is a solution of $ x^{p}\equiv \alpha\; (\text{mod} \; m) $. Next we show that this solution is unique modulo $ m. $ Since $ p \nmid \phi (m), $ so $ gcd (p, \phi (p^{'})) = 1. $ Then the linear congruence $ py \equiv 1 \; (\text{mod} \; p^{'}-1) $ has a unique solution in $ y. $ Finally, we put $ \beta \equiv \alpha^{y}\; (\text{mod} \; p^{'}) $ to get $ \beta^{p}\equiv \alpha^{p.y} \equiv a\; (\text{mod} \; p^{'}) $. By Chinese Reminder Theorem, we get that $ \beta $ is a unique solution of $ x^{p} \equiv \alpha\; (\text{mod} \; m) $. Thus, indegree of this arbitrary vertex is one. This certainly implies that every vertex is either a loop (a cycle of length one) or at some cycle. The converse is a direct consequence of Lemma 3.1.

For further result on semiregularity, we define a function $ \eta $ as,

where $ \eta_{o}(m) $ is the number distinct prime divisors of $ m $ such that $ p^{'}\equiv1 (\text{mod} \; p). $ In the following theorem, we characterize the semiregularity of $ G_{1}(p, m) $, where $ p $ is an odd prime.

Theorem 3.3. The digraph $ G_{1}(p, m) $ is semiregular if and only if $ p|\phi(m), $ Also the indegrees in $ G_{1}(p, m) $ are either $ p^{\; \eta(p)} $ or zero.

Proof. By definition of digraph $ G_{1}(p, m) $, it is indicated, that $ \beta^{\phi(m)}\equiv 1 \; (\text{mod} \; m) $ for each vertex $ \beta $ in $ G_{1}(p, m). $ This means that the indegrees of the vertices of $ G_{1}(p, m) $ are same if $ indeg(\beta) > 0 $. To find the $ indeg(\beta) > 0 $, we just count the indegrees of 1. For this purpose we just count the number of solutions of the congruence, $ x^{p}\equiv 1 \; (\text{mod} \; p^r $). Let $ p $ be an odd prime and $ r $ be any positive integer. Then we see that, $ (p^{r-1}+1)^{p}\equiv 1 \; (\text{mod} \; p^r). $ Likewise, we see that the numbers, $ 2\times p^{r-1}+1, 3\times p^{r-1}+1, 4\times p^{r-1}+1, 5\times p^{r-1}+1, 6\times p^{r-1}+1, \dotso, p\times p^{r-1}+1 $ also solutions of the congruence, $ x^{p}\equiv 1 \; (\text{mod} \; p^r $). While modulo $ p^{'}, $ there are always $ p^{'} $ solutions whenever $ p^{'} \equiv 1 \; (\text{mod} \; p) $ and there is a trivial solution if $ p^{'} \not\equiv 1 \; (\text{mod} \; p) $ (for detail see ^[26], page 104). Using the canonical representation of $ m $ into odd primes and Chinese Remainder Theorem, simultaneously, we must get that $ \alpha^p\equiv 1\; (\text{mod} \; m) $ either have $ p^{\; \eta(m)} $ solutions or have no solution for each vertex $ \alpha $ in $ G_{1}(p, m). $ On the other hand, we let $ G_{1}(p, m) $ is semiregular and $ indeg(\alpha) = p^{\; \eta(m)} $ for $ \alpha\in G_{1}(p, m). $ This means that $ \alpha^{p}\equiv 1\; (\text{mod} \; m). $ Using multiplicative order and Euler Theorem for $ \alpha, $ we deduce that $ p\mid \phi(m). $ Conversely, assume that $ p\nmid \phi(m). $ then by Lemma 3.2 indegree of each vertex is one which is contradiction. Hence $ p\mid \phi(m). $

Figure 6 reflects Theorem 3.3.

Figure 6.  The digraph $G (11, 67)$.

DownLoad: Full-Size Img PowerPoint

4.   Conclusions

Until the date, several papers on power diagraphs have been published for the fixed power of the congruences modulo an integer. For example, power diagraphs corresponding to $ x^{2} = y\; (\text{mod} \; m) $, $ x^{3} = y\; (\text{mod}\; m) $ or else fixed powers have been discussed earlier. In this work, we discussed and generalized the results of power diagraphs for any odd prime $ p $ as $ x $ power rather fixing. That is, for the congruence of $ x^{p} = y\; (\text{mod}\; m) $, where $ p $ is any odd prime. We addressed the number of loops, cyclic structures, tree structures and the enumeration of components over residue classes of integers. In Section 1, the fixed points of such diagraphs are described and enumerated. These fixed points are referred to as loops. The existence and enumeration of cycles along with their sizes are discussed in Theorems 2.1–2.4 and in Corollary 2.5. In Theorems 2.6–2.11, we have discussed the enumeration of components and trees for classes of integers. These findings have also been shown in Figures 2–5 for better comprehension and confirmation. Finally, the results on regularity and semi-regularity are discussed and generalized in Section 3. In fact, we have fully established and defined the desired ideas for power diagraphs with an odd prime power. We believe that the characterizations can be built on the basis of these findings for all composite modules, which can serve as a basis for solving many difficult and open challenges.

Acknowledgment

This work was funded by the Deanship of Scientific Research (DSR) at King Abdulaziz University, Jeddah. The authors, therefore, acknowledge with thanks DSR for technical and financial support.

Conflict of interest

The authors declare that they have no conflict of interest regarding the publication of the research article.