Symmetric Digraphs from Powers Modulo n

Guixin Deng, Pingzhi Yuan
DOI: 10.4236/ojdm.2011.13013                

Abstract

For each pair of positive integers n and k, let G(n,k) denote the digraph whose set of vertices is H = {0,1,2,···, n – 1} and there is a directed edge from a ∈ H to b ∈ H if a ≡ b(mod n). The digraph G(n,k) is symmetric if its connected component can be partitioned into isomorphic pairs. In this paper we obtain all symmetric G(n,k)

Keywords

Congruence, Digraph, Component, Height, Cycle

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	W. Carlip and M. Mincheva, “Symmetry of Iteration Digraphs,” Czechoslovak Mathematic Journal, Vol. 58, No. 1, 2008, pp. 131-145. doi:10.1007/s10587-008-0009-8
[2]	G. Chartrand and L. Lesnidk, “Graphs and Digraphs (3rd Edition),” Chapman Hall, London, 1996.
[3]	Wun-Seng Chou and Igor E. Shparlinski, “On the Cycle Structure of Repeated Exponentiation Modulo a Prime,” Journal of Number Theory, Vol.107, No. 2, 2004, pp. 345-356. doi:10.1016/j.jnt.2004.04.005
[4]	Joe Kramer-Miller, “Structural Properties of Power Digraphs Mudulo n,” Manuscript.
[5]	M. Krizek, F. Lucas and L. Somer, “17 Lectures on the Femat Numbers, from Number Theory to Geometry,” Springer, New York, 2001.
[6]	C. Lucheta, E. Miller and C. Reiter, “Digraphs from Powers Modulo p,” Fibonacci Quart, Vol. 34, 1996, pp. 226-239.
[7]	I. Niven, H. S. Zuckerman and H. L. Montgomery, “An Introduction to the Theory of Numbers,” 5th Edition, John Wiley & Sons, New York, 1991.
[8]	T. D. Rogers, “The Graph of the Square Mapping on the Prime Fields,” Discrete Mathematics, Vol. 148, No. 1-23, 1996, pp. 317-324. doi:10.1016/0012-365X(94)00250-M
[9]	L. Somer and M. Krizek, “On a Connection of Number Theory with Graph Theory,” Czechoslovak Mathematic Journal, Vol. 54, No. 2, 2004, pp. 465-485. doi:10.1023/B:CMAJ.0000042385.93571.58
[10]	L. Somer and M. Krizek, “Structure of Digrphs Associated with Quadratic Congruences with Composite Moduli,” Discrete Mathematics, Vol. 306, No. 18, 2006, pp. 2174-2185. doi:10.1016/j.disc.2005.12.026
[11]	L. Somer and M. Krizek, “On Semiregular Digraphs of the Congruence xk ≡ y(mod n),” Commentationes Mathematicae Universitatis Carolinae, Vol. 48, No. 1, 2007, pp. 41-58.
[12]	L. Szalay, “A Discrete Iteration in Number Theory,” BDTF Tud. KAozl, Vol. 8, 1992, pp. 71-91.
[13]	L. Somer and M. Krizek, “On Symmetric Digrphs of the Congruence xk ≡ y (mod n),” Discrete Mathematics, Vol. 309, No. 8, 2009, pp. 1999-2009. doi:10.1016/j.disc.2008.04.009
[14]	B. Wilson, “Power Digraphs Modulo n,” Fibonacci Quart, Vol. 36, 1998, pp. 229-239.