×

On the heights of power digraphs modulo \(n\). (English) Zbl 1265.05274

To each pair of positive integers \(k\geq 2\) and \(n\) a digraph \(G(n,k)\) is assigned whose set of vertices is \(\{0,1,\dots ,n-1\}\) and \(\{(a,b)\: a^k\equiv b\pmod n\}\) is the set of its directed edges. The authors define the height of each vertex \(a\) as the shortest distance to the unique cycle of the component of \(G(n,k)\) that contains \(a\). They establish necessary and sufficient conditions on \(n\) such that each vertex of indegree 0 of a certain subdigraph of \(G(n,k)\) is at height \(q\geq 1\).
Reviewer: Michal Krizek

MSC:

05C20 Directed graphs (digraphs), tournaments
11A07 Congruences; primitive roots; residue systems
11A15 Power residues, reciprocity
20K01 Finite abelian groups

Software:

Graphviz; Matlab
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] D.M. Burton: Elementary Number Theory. McGraw-Hill, 2007.
[2] W. Carlip, M. Mincheva: Symmetry of iteration graphs. Czech. Math. J. 58 (2008), 131–145. · Zbl 1174.05048
[3] R.D. Carmichael: Note on a new number theory function. Am. Math. Soc. Bull. 16 (1910), 232–238. · JFM 41.0226.04
[4] G. Chartrand, O.R. Oellermann: Applied and Algorithmic Graph Theory. International Series in Pure and Applied Mathematics, McGraw-Hill, 1993.
[5] N. Deo: Graph theory with Application to Engineering and Computer Sciences. Prentice-Hall Series in Automatic Computation. Englewood Cliffs, N.J.: Prentice-Hall, 1974.
[6] J. Ellson, E. Gansner, L. Koutsofios, S.C. North, G. Woodhull: Graphviz-open source graph drawing tools.. Mutzel, Petra (ed.) et al., Graph drawing. 9th international symposium, GD 2001, Vienna, Austria, September 23–26, 2001; Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 2265 (2002), 483–484. · Zbl 1054.68583
[7] S.M. Husnine, U. Ahmad, L. Somer: On symmetries of power digraphs. Util. Math. 85 (2011), 257–271. · Zbl 1251.05066
[8] J. Kramer-Miller: Structural properties of power digraphs modulo n. Proceedings of the 2009 Midstates Conference on Undergraduate Research in Computer Science and Mathematics, Oberlin, Ohio (2009), 40–49.
[9] C. Lucheta, E. Miller, C. Reiter: Digraphs from powers modulo p. Fibonacci Q. 34 (1996), 226–239. · Zbl 0855.05067
[10] L. Somer, M. Křžek: On a connection of number theory with graph theory. Czech. Math. J. 54 (2004), 465–485. · Zbl 1080.11004
[11] L. Somer, M. Křžek: Structure of digraphs associated with quadratic congruences with composite moduli. Discrete Math. 306 (2006), 2174–2185. · Zbl 1161.05323
[12] L. Somer, M. Křžek: On semiregular digraphs of the congruence x k y (mod n). Commentat. Math. Univ. Carol. 48 (2007), 41–58. · Zbl 1174.05058
[13] L. Somer, M. Křžek: On symmetric digraphs of the congruence x k y (mod n). Discrete Math. 309 (2009), 1999–2009. · Zbl 1208.05041
[14] B. Wilson: Power digraphs modulo n. Fibonacci Q. 36 (1998), 229–239. · Zbl 0936.05049
[15] MATLAB, The language of technical computing (version 7.0.0.19920 (R14)).
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.