On the heights of power digraphs modulo $n$

Ahmad, Uzma ; Syed, Husnine

Czechoslovak Mathematical Journal, Tome 62 (2012) no. 2, pp. 541-556.

Résumé

A power digraph, denoted by $G(n,k)$, is a directed graph with ${\mathbb{Z}}_n=\{0,1,\dots ,n-1\}$ as the set of vertices and $E=\{(a,b):a^k\equiv b(\mathrm{mod}n)\}$ as the edge set. In this paper we extend the work done by Lawrence Somer and Michal Křížek: On a connection of number theory with graph theory, Czech. Math. J. 54 (2004), 465–485, and Lawrence Somer and Michal Křížek: Structure of digraphs associated with quadratic congruences with composite moduli, Discrete Math. 306 (2006), 2174–2185. The heights of the vertices and the components of $G(n,k)$ for $n\ge 1$ and $k\ge 2$ are determined. We also find an expression for the number of vertices at a specific height. Finally, we obtain 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\ge 1$.

Détail

DOI : 10.1007/s10587-012-0028-3

Classification : 05C20, 11A07, 11A15, 20K01
Mots-clés : iteration digraph; height; Carmichael lambda function; fixed point; regular digraph