On the symmetric digraphs from powers modulo \(n\). (English) Zbl 1238.05104

Summary: For any positive integers \(n\) and \(k\), let \(G(n,k)\) denote the digraph whose set of vertices is \(H=\{0,1,2,\ldots ,n - 1\}\) and there is a directed edge from \(a\in H\) to \(b\in H\) if \(a^k \equiv b\pmod n\). The digraph \(G(n,k)\) is called symmetric of order \(M\) if its set of connected components can be partitioned into subsets of size \(M\) with each subset containing \(M\) isomorphic components. In this paper, we establish a necessary and sufficient condition for \(G(n,k)\) to be symmetric of order \(M\), where \(M\) has an odd prime divisor.


05C20 Directed graphs (digraphs), tournaments
11A07 Congruences; primitive roots; residue systems
05C75 Structural characterization of families of graphs
11A15 Power residues, reciprocity
11T99 Finite fields and commutative rings (number-theoretic aspects)
Full Text: DOI


[1] Carlip, W.; Mincheva, M., Symmetry of iteration digraphs, Czechoslovak Math. J., 58, 131-145 (2008) · Zbl 1174.05048
[2] J. Kramer-Miller, Structural properties of power digraphs modulo \(n\); J. Kramer-Miller, Structural properties of power digraphs modulo \(n\)
[3] Křížek, M.; Lucas, F.; Somer, L., 17 Lectures on the Fermat Numbers: From Number Theory to Geometry (2001), Springer: Springer New York · Zbl 1010.11002
[4] Somer, L.; Křížek, M., On a connection of number theory with graph theory, Czechoslovak Math. J., 54, 465-485 (2004) · Zbl 1080.11004
[5] Somer, L.; Křížek, M., On semiregular digraphs of the congruence \(x^k \equiv y(mod) n\), Comment. Math. Univ. Carolin., 48, 1, 41-58 (2007) · Zbl 1174.05058
[6] Somer, L.; Křížek, M., On symmetric digrphs of the congruence \(x^k \equiv y(mod) n\), Discrete Math., 309, 1999-2009 (2009) · Zbl 1208.05041
[7] Szalay, L., A discrete iteration in number theory, BDTF Tud. Közl., 8, 71-91 (1992) · Zbl 0801.11011
[8] Wilson, B., Power digraphs modulo \(n\), Fibonacci Quart., 36, 229-239 (1998) · Zbl 0936.05049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.