In this work, we incorporate modular arithmetic and discuss a special class of graphs based on power functions in a given modulus, called power digraphs. In power digraphs, the study of cyclic structures and enumeration of components is a difficult task. In this manuscript, we attempt to solve the problem for $ p $th power congruences over different classes of residues, where $ p $ is an odd prime. For any positive integer $ m $, we build a digraph $ G(p, m) $ whose vertex set is $ \mathbb{Z}_{m} = \{0, 1, 2, 3, ..., m-1\} $ and there will be a directed edge from vertices $ u\in \mathbb{Z}_{m} $ to $ v\in \mathbb{Z}_{m} $ if and only if $ u^{p}\equiv v\; (\text{mod} \; m) $. We study the structures of $ G(p, m) $. For the classes of numbers $ 2^{r} $ and $ p^{r} $ where $ r\in \mathbb{Z^{+}} $, we classify cyclic vertices and enumerate components of $ G(p, m) $. Additionally, we investigate two induced subdigraphs of $ G(p, m) $ whose vertices are coprime to $ m $ and not coprime to $ m $, respectively. Finally, we characterize regularity and semiregularity of $ G(p, m) $ and establish some necessary conditions for cyclicity of $ G(p, m) $.
Citation: M. Haris Mateen, Muhammad Khalid Mahmmod, Dilshad Alghazzawi, Jia-Bao Liu. Structures of power digraphs over the congruence equation $ x^p\equiv y\; (\text{mod}\; m) $ and enumerations[J]. AIMS Mathematics, 2021, 6(5): 4581-4596. doi: 10.3934/math.2021270
In this work, we incorporate modular arithmetic and discuss a special class of graphs based on power functions in a given modulus, called power digraphs. In power digraphs, the study of cyclic structures and enumeration of components is a difficult task. In this manuscript, we attempt to solve the problem for $ p $th power congruences over different classes of residues, where $ p $ is an odd prime. For any positive integer $ m $, we build a digraph $ G(p, m) $ whose vertex set is $ \mathbb{Z}_{m} = \{0, 1, 2, 3, ..., m-1\} $ and there will be a directed edge from vertices $ u\in \mathbb{Z}_{m} $ to $ v\in \mathbb{Z}_{m} $ if and only if $ u^{p}\equiv v\; (\text{mod} \; m) $. We study the structures of $ G(p, m) $. For the classes of numbers $ 2^{r} $ and $ p^{r} $ where $ r\in \mathbb{Z^{+}} $, we classify cyclic vertices and enumerate components of $ G(p, m) $. Additionally, we investigate two induced subdigraphs of $ G(p, m) $ whose vertices are coprime to $ m $ and not coprime to $ m $, respectively. Finally, we characterize regularity and semiregularity of $ G(p, m) $ and establish some necessary conditions for cyclicity of $ G(p, m) $.
| [1] | S. Bryant, Groups, graphs, and Fermat's last theorem, Am. Math. Monthly, 74 (1967), 152–155. |
| [2] | L. Szalay, A discrete iteration in number theory, BDTF Tud. Közl., 8 (1992), 71–91. |
| [3] |
T. D. Rogers, The graph of the square mapping on the prime fields, Discrete Math., 148 (1996), 317–324. doi: 10.1016/0012-365X(94)00250-M
|
| [4] | L. Somer, M. Krizek, On a connection of number theory with graph theory, Czech. Math. J., 5 (2004), 465–485. |
| [5] | M. K. Mahmood, F. Ahmad, An informal enumeration of squares of $2^k$ using rooted trees arising from congruences, Utilitas Math., 105 (2017), 41–51. |
| [6] | M. A Malik, M. K Mahmood, On simple graphs arising from exponential congruences, J. Appl. Math., 2012 (2012), 1–10. |
| [7] |
Y. J. Wei, G. Tang, The iteration digraphs of finite commutative rings, Turk. J. Math., 39 (2015), 872–883. doi: 10.3906/mat-1503-2
|
| [8] |
L. Somer, M. Krizek, On symmetric digraphs of the congruence $x^{k}\equiv y ({\rm{mod}}\; m)$, Discrete Math., 309 (2009), 1999–2009. doi: 10.1016/j.disc.2008.04.009
|
| [9] | J. Skowronek-Kazió, Some digraphs arising from number theory and remarks on the zero-divisor graph of the ring $Z_{n}$, Inf. Process. Lett., 108 (2008), 165–169. |
| [10] | M. H. Mateen, M. K. Mahmood, A new approch for the enumeration of components of digraphs over the quadratic maps, J. Prime Res. Math., 16 (2020), 56–66. |
| [11] |
M. K. Mahmood, F. Ahmad, A classification of cyclic nodes and enumerations of components of a class of discrete graphs, Appl. Math. Inf. Sci., 9 (2015), 103–112. doi: 10.12785/amis/090115
|
| [12] | M. H. Mateen, M. K. Mahmood, Power digraphs associated with the congruence $x^{n}\equiv y ({\rm{mod}}\; m)$, Punjab Univ. J. Math., 51 (2019), 93–102. |
| [13] | M. H. Mateen, M. K. Mahmood, S. Ali, Importance of power digraph in computer science, International conference on innovative computing (ICIC), Lahore, Pakistan, (2019), 1–6. |
| [14] |
S. Akbari, A. Mohammadian, On the zero-divisor graph of a commutative ring, J. Algebra, 274 (2004), 847–855. doi: 10.1016/S0021-8693(03)00435-6
|
| [15] | Y. J. Wei, J. Z. Nan, G. H. Tang, H. D. Su, The cubic mapping graphs of the residue classes of integers, Ars Combin., 97 (2010), 101–110. |
| [16] |
Y. Wei, G. Tang, H. Su, The square mapping graphs of finite commutative rings, Algebra Colloq., 19 (2012), 569–580. doi: 10.1142/S1005386712000442
|
| [17] | M. Rezaei, S. U. Rehman, Z. U. Khan, A. Q. Baig, M. R. Farahani, Quadratic residues graph, Int. J. Pure Appl. Math., 113 (2017), 465–470. |
| [18] | W. Carlip, M. Mincheva, Symmetry of iteration graphs, Czechoslovak Math. J., 58 (2008), 131–145. |
| [19] |
G. Deng, P. Yuan, On the symmetric digraphs from powers modulo $n$, Discrete Math., 312 (2012), 720–728. doi: 10.1016/j.disc.2011.11.007
|
| [20] |
Y. Meemark, N. Wiroonsri, The quadratic digraph on polynomial rings over finite fields, Finite Fields Appl., 16 (2010), 334–346. doi: 10.1016/j.ffa.2010.05.004
|
| [21] |
Y. Meemark, N. Wiroonsri, The digraph of the kth power mapping of the quotient ring of polynomials over finite fields, Finite Fields Appl., 18 (2012), 179–191. doi: 10.1016/j.ffa.2011.07.008
|
| [22] | M. K. Mahmood, S. Ali, A novel labeling algorithm on several classes of graphs, Punjab Univ. J. Math., 49 (2017), 23–35. |
| [23] | S. Ali, M. K. Mahmood, New numbers on euler totient function with application, J. Math. Ext., 14 (2019), 61–83. |
| [24] |
H. Alolaiyan, A. Yousaf, M. Ameer, A. Razaq, Non-conjugate graphs associated with finite groups, IEEE Access, 7 (2019), 122849–122853. doi: 10.1109/ACCESS.2019.2938083
|
| [25] |
A. Portilla, J. M. Rodrguez, J. M. Sigarreta, E. Tours, Gromov hyperbolicity in directed graphs, Symmetry, 12 (2020), 105–117. doi: 10.3390/sym12010105
|
| [26] | I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, Hoboken: John Wiley & Sons Inc., 1991. |
| [27] |
R. D. Carmichael, Note on a new number theory function, Bull. Am. Math. Soc., 16 (1910), 232–238. doi: 10.1090/S0002-9904-1910-01892-9
|
| [28] | B. Wilson, Power digraphs modulo $n$, Fibonacci Quart., 36 (1996), 229–239. |
| [29] | M. K. Mahmood, S. Ali, On super totient numbers with applications and algorithms to graph labeling, Ars Combinatoria, 143 (2019), 29–37. |
Figures(6)
M. Haris Mateen, Muhammad Khalid Mahmmod, Dilshad Alghazzawi, Jia-Bao Liu. Structures of power digraphs over the congruence equation $ x^p\equiv y\; (\text{mod}\; m) $ and enumerations[J]. AIMS Mathematics, 2021, 6(5): 4581-4596. doi: 10.3934/math.2021270
DownLoad: