| Title:
|
On the heights of power digraphs modulo $n$ (English) |
| Author:
|
Ahmad, Uzma |
| Author:
|
Syed, Husnine |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
62 |
| Issue:
|
2 |
| Year:
|
2012 |
| Pages:
|
541-556 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
iteration digraph |
| Keyword:
|
height |
| Keyword:
|
Carmichael lambda function |
| Keyword:
|
fixed point |
| Keyword:
|
regular digraph |
| MSC:
|
05C20 |
| MSC:
|
11A07 |
| MSC:
|
11A15 |
| MSC:
|
20K01 |
| idZBL:
|
Zbl 1265.05274 |
| idMR:
|
MR2990193 |
| DOI:
|
10.1007/s10587-012-0028-3 |
| . |
| Date available:
|
2012-06-08T09:52:21Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/142845 |
| . |
| Reference:
|
[1] Burton, D. M.: Elementary Number Theory.McGraw-Hill (2007). MR 0567137 |
| Reference:
|
[2] Carlip, W., Mincheva, M.: Symmetry of iteration graphs.Czech. Math. J. 58 (2008), 131-145. Zbl 1174.05048, MR 2402530, 10.1007/s10587-008-0009-8 |
| Reference:
|
[3] Carmichael, R. D.: Note on a new number theory function.Am. Math. Soc. Bull. 16 (1910), 232-238. MR 1558896, 10.1090/S0002-9904-1910-01892-9 |
| Reference:
|
[4] Chartrand, G., Oellermann, O. R.: Applied and Algorithmic Graph Theory.International Series in Pure and Applied Mathematics McGraw-Hill (1993) \MR 1211413. MR 1211413 |
| Reference:
|
[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 0360322 |
| Reference:
|
[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. Zbl 1054.68583, MR 1962414 |
| Reference:
|
[7] Husnine, S. M., Ahmad, U., Somer, L.: On symmetries of power digraphs.Util. Math. 85 (2011), 257-271. MR 2840802 |
| Reference:
|
[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. |
| Reference:
|
[9] Lucheta, C., Miller, E., Reiter, C.: Digraphs from powers modulo $p$.Fibonacci Q. 34 (1996), 226-239. Zbl 0855.05067, MR 1390409 |
| Reference:
|
[10] Somer, L., Křížek, M.: On a connection of number theory with graph theory.Czech. Math. J. 54 (2004), 465-485. MR 2059267, 10.1023/B:CMAJ.0000042385.93571.58 |
| Reference:
|
[11] Somer, L., Křížek, M.: Structure of digraphs associated with quadratic congruences with composite moduli.Discrete Math. 306 (2006), 2174-2185. MR 2255611, 10.1016/j.disc.2005.12.026 |
| Reference:
|
[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 2338828 |
| Reference:
|
[13] Somer, L., Křížek, M.: On symmetric digraphs of the congruence $x^{k}\equiv y \pmod n$.Discrete Math. 309 (2009), 1999-2009. MR 2510326, 10.1016/j.disc.2008.04.009 |
| Reference:
|
[14] Wilson, B.: Power digraphs modulo $n$.Fibonacci Q. 36 (1998), 229-239. Zbl 0936.05049, MR 1627384 |
| Reference:
|
[15] : MATLAB, The language of technical computing (version 7.0.0.19920 (R14)).. |
| . |
