×

Symmetry of iteration graphs. (English) Zbl 1174.05048

Summary: We examine iteration graphs of the squaring function on the rings \(\mathbb Z/n\mathbb Z \) when \(n = 2^{k}p\), for \(p\) a Fermat prime. We describe several invariants associated with these graphs and use them to prove that the graphs are not symmetric when \(k = 3\) and when \(k \geq 5\) and are symmetric when \(k = 4\).

MSC:

05C20 Directed graphs (digraphs), tournaments
11T99 Finite fields and commutative rings (number-theoretic aspects)

Software:

GAP; Graphviz
PDF BibTeX XML Cite
Full Text: DOI EuDML Link

References:

[1] Earle L. Blanton, Jr., Spencer P. Hurd and Judson S. McCranie: On a digraph defined by squaring modulo n. Fibonacci Quart. 30 (1992), 322–334. · Zbl 0767.05050
[2] Guy Chassé: Combinatorial cycles of a polynomial map over a commutative field. Discrete Math. 61 (1986), 21–26. · Zbl 0596.12020
[3] John Ellson, Emden Gansner, Lefteris Koutsofios, Stephen C. North and Gordon Woodhull: Graphviz-open source graph drawing tools. Graph drawing (Petra Mutzel, Michael Jünger, and Sebastian Leipert, eds.), Lecture Notes in Computer Science, vol. 2265, Springer-Verlag, Berlin, 2002, Selected papers from the 9th International Symposium (GD 2001) held in Vienna, September 23–26, 2001, pp. 483–484. (In English.) · Zbl 1054.68583
[4] The GAP Group, Gap-groups, algorithms, and programming, version 4.4, 2005, ( http://www.gap-system.org ).
[5] Thomas D. Rogers: The graph of the square mapping on the prime fields. Discrete Math. 148 (1996), 317–324. · Zbl 0843.05048
[6] Lawrence Somer and Michal Křížek: On a connection of number theory with graph theory. Czechoslovak Math. J. 54 (2004), 465–485. · Zbl 1080.11004
[7] L. Szalay: A discrete iteration in number theory. BDTF Tud. Közl. 8 (1992), 71–91. · Zbl 0801.11011
[8] Troy Vasiga and Jeffrey Shallit: On the iteration of certain quadratic maps over GF(p). Discrete Math. 277 (2004), 219–240. · Zbl 1045.11086
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.