Geodesic
On the heights of power digraphs modulo $n$
Czechoslovak Mathematical Journal, Tome 62 (2012) no. 2, pp. 541-556
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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)\colon a^{k}\equiv b\pmod 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\geq 1$ and $k\geq 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\geq 1$.
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)\colon a^{k}\equiv b\pmod 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\geq 1$ and $k\geq 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\geq 1$.
DOI : 10.1007/s10587-012-0028-3
Classification : 05C20, 11A07, 11A15, 20K01
Keywords: iteration digraph; height; Carmichael lambda function; fixed point; regular digraph 
@article{10_1007_s10587_012_0028_3,
     author = {Ahmad, Uzma and Syed, Husnine},
     title = {On the heights of power digraphs modulo $n$},
     journal = {Czechoslovak Mathematical Journal},
     pages = {541--556},
     year = {2012},
     volume = {62},
     number = {2},
     doi = {10.1007/s10587-012-0028-3},
     mrnumber = {2990193},
     zbl = {1265.05274},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-012-0028-3/}
}
TY  - JOUR
AU  - Ahmad, Uzma
AU  - Syed, Husnine
TI  - On the heights of power digraphs modulo $n$
JO  - Czechoslovak Mathematical Journal
PY  - 2012
SP  - 541
EP  - 556
VL  - 62
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-012-0028-3/
DO  - 10.1007/s10587-012-0028-3
LA  - en
ID  - 10_1007_s10587_012_0028_3
ER  - 
%0 Journal Article
%A Ahmad, Uzma
%A Syed, Husnine
%T On the heights of power digraphs modulo $n$
%J Czechoslovak Mathematical Journal
%D 2012
%P 541-556
%V 62
%N 2
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-012-0028-3/
%R 10.1007/s10587-012-0028-3
%G en
%F 10_1007_s10587_012_0028_3
Ahmad, Uzma; Syed, Husnine. On the heights of power digraphs modulo $n$. Czechoslovak Mathematical Journal, Tome 62 (2012) no. 2, pp. 541-556. doi: 10.1007/s10587-012-0028-3

[1] Burton, D. M.: Elementary Number Theory. McGraw-Hill (2007). | MR

[2] Carlip, W., Mincheva, M.: Symmetry of iteration graphs. Czech. Math. J. 58 (2008), 131-145. | DOI | MR | Zbl

[3] Carmichael, R. D.: Note on a new number theory function. Am. Math. Soc. Bull. 16 (1910), 232-238. | DOI | MR

[4] Chartrand, G., Oellermann, O. R.: Applied and Algorithmic Graph Theory. International Series in Pure and Applied Mathematics McGraw-Hill (1993) \MR 1211413. | MR

[5] Deo, N.: Graph theory with Application to Engineering and Computer Sciences. Prentice-Hall Series in Automatic Computation. Englewood Cliffs, N.J.: Prentice-Hall (1974). | MR

[6] Ellson, J., Gansner, E., Koutsofios, L., North, S. C., Woodhull, G.: 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. | MR | Zbl

[7] Husnine, S. M., Ahmad, U., Somer, L.: On symmetries of power digraphs. Util. Math. 85 (2011), 257-271. | MR

[8] Kramer-Miller, J.: 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] Lucheta, C., Miller, E., Reiter, C.: Digraphs from powers modulo $p$. Fibonacci Q. 34 (1996), 226-239. | MR | Zbl

[10] Somer, L., Křížek, M.: On a connection of number theory with graph theory. Czech. Math. J. 54 (2004), 465-485. | DOI | MR

[11] Somer, L., Křížek, M.: Structure of digraphs associated with quadratic congruences with composite moduli. Discrete Math. 306 (2006), 2174-2185. | DOI | MR

[12] Somer, L., Křížek, M.: On semiregular digraphs of the congruence $x^{k}\equiv y \pmod n$. Commentat. Math. Univ. Carol. 48 (2007), 41-58. | MR

[13] Somer, L., Křížek, M.: On symmetric digraphs of the congruence $x^{k}\equiv y \pmod n$. Discrete Math. 309 (2009), 1999-2009. | DOI | MR

[14] Wilson, B.: Power digraphs modulo $n$. Fibonacci Q. 36 (1998), 229-239. | MR | Zbl

[15] MATLAB, The language of technical computing (version 7.0.0.19920 (R14)).

Cité par Sources :