Previous |  Up |  Next


iteration digraph; isolated fixed points; Charmichael lambda function; Fermat numbers; Regular digraphs
A power digraph modulo $n$, denoted by $G(n,k)$, is a directed graph with $Z_{n}=\{0,1,\dots, n-1\}$ as the set of vertices and $E=\{(a,b): a^{k}\equiv b\pmod n\}$ as the edge set, where $n$ and $k$ are any positive integers. In this paper we find necessary and sufficient conditions on $n$ and $k$ such that the digraph $G(n,k)$ has at least one isolated fixed point. We also establish necessary and sufficient conditions on $n$ and $k$ such that the digraph $G(n,k)$ contains exactly two components. The primality of Fermat number is also discussed.
[1] Wilson B.: Power digraphs modulo $n$. Fibonacci Quart. 36 (1998), 229–239. MR 1627384 | Zbl 0936.05049
[2] Lucheta C., Miller E., Reiter C.: Digraphs from powers modulo $p$. Fibonacc Quart. 34 (1996), 226–239. MR 1390409 | Zbl 0855.05067
[3] Burton D.M.: Elementary Number Theory. McGraw-Hill, 2007. Zbl 1084.11001
[4] Chartrand G., Oellermann O.R.: Applied and Algorithmic Graph Theory. McGraw-Hill, New York, 1993. MR 1211413
[5] Kramer-Miller J.: Structural properties of power digraphs modulo $n$. in Proceedings of the 2009 Midstates Conference for Undergraduate Research in Computer Science and Mathematics, Oberlin, Ohio, 2009, pp. 40–49.
[6] Ellson J., Gansner E., Koutsofios L., North S.C., Woodhull G.: Graphviz - open source graph drawing tools. version $2.26.3$, Zbl 1054.68583
[7] Somer L., Křížek M.: On a connection of number theory with graph theory. Czechoslovak Math. J. 54 (2004), 465–485. DOI 10.1023/B:CMAJ.0000042385.93571.58 | MR 2059267
[8] Somer L., Křížek M.: Structure of digraphs associated with quadratic congruences with composite moduli. Discrete Math. 306 (2006), 2174–2185. DOI 10.1016/j.disc.2005.12.026 | MR 2255611
[9] Somer L., Křížek M.: On semi-regular digraphs of the congruence $x^{k}\equiv y \pmod n$. Comment. Math. Univ. Carolin. 48 (2007), no. 1, 41–58. MR 2338828
[10] Somer L., Křížek M.: On symmetric digraphs of the congruence $x^{k}\equiv y \pmod n$. Discrete Math. 309 (2009), 1999–2009. DOI 10.1016/j.disc.2008.04.009
[11] Szalay L.: A discrete iteration in number theory. BDTF Tud. Közl. 8 (1992), 71–91. Zbl 0801.11011
[12] MATLAB,: The language of technical computing. version (R14).
[13] Deo N.: Graph theory with Application to Engineering and Computer Sciences. Prentice-Hall of India private Limited, 1990. MR 0360322
[14] Carmichael R.D.: Note on a new number theory function. Bull. Amer. Math. Soc. 16 (1910), 232–238. DOI 10.1090/S0002-9904-1910-01892-9 | MR 1558896
[15] Husnine S.M., Ahmad U., Somer L.: On symmetries of power digraphs. Utilitas Mathematica(to appear). MR 2840802
[16] Skowronek-Kaziów J.: Properties of digraphs connected with some congruences relations. Czechoslovak Math. J. 59 (2009), 39–49. DOI 10.1007/s10587-009-0003-9 | MR 2486614
Partner of
EuDML logo