On the heights of power digraphs modulo n

Uzma Ahmad; Husnine Syed

Czechoslovak Mathematical Journal (2012)

  • Volume: 62, Issue: 2, page 541-556
  • ISSN: 0011-4642

Abstract

top
A power digraph, denoted by G ( n , k ) , is a directed graph with ℤ n = { 0 , 1 , ⋯ , n - 1 } as the set of vertices and E = { ( a , b ) : a k ≡ b ( 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 ≥ 1 and k ≥ 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 ≥ 1 .

How to cite

top

Ahmad, Uzma, and Syed, Husnine. "On the heights of power digraphs modulo $n$." Czechoslovak Mathematical Journal 62.2 (2012): 541-556. <http://eudml.org/doc/246239>.

@article{Ahmad2012,
abstract = {A power digraph, denoted by $G(n,k)$, is a directed graph with $\mathbb \{Z\}_\{n\}=\lbrace 0,1,\dots ,n-1\rbrace $ as the set of vertices and $E=\lbrace (a,b)\colon a^\{k\}\equiv b\hspace\{4.44443pt\}(\@mod \; n)\rbrace $ 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$.},
author = {Ahmad, Uzma, Syed, Husnine},
journal = {Czechoslovak Mathematical Journal},
keywords = {iteration digraph; height; Carmichael lambda function; fixed point; regular digraph; iteration digraph; height; Carmichael lambda function; fixed point; regular digraph},
language = {eng},
number = {2},
pages = {541-556},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On the heights of power digraphs modulo $n$},
url = {http://eudml.org/doc/246239},
volume = {62},
year = {2012},
}

TY - JOUR
AU - Ahmad, Uzma
AU - Syed, Husnine
TI - On the heights of power digraphs modulo $n$
JO - Czechoslovak Mathematical Journal
PY - 2012
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 62
IS - 2
SP - 541
EP - 556
AB - A power digraph, denoted by $G(n,k)$, is a directed graph with $\mathbb {Z}_{n}=\lbrace 0,1,\dots ,n-1\rbrace $ as the set of vertices and $E=\lbrace (a,b)\colon a^{k}\equiv b\hspace{4.44443pt}(\@mod \; n)\rbrace $ 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$.
LA - eng
KW - iteration digraph; height; Carmichael lambda function; fixed point; regular digraph; iteration digraph; height; Carmichael lambda function; fixed point; regular digraph
UR - http://eudml.org/doc/246239
ER -

References

top
  1. Burton, D. M., Elementary Number Theory, McGraw-Hill (2007). (2007) MR0567137
  2. Carlip, W., Mincheva, M., 10.1007/s10587-008-0009-8, Czech. Math. J. 58 (2008), 131-145. (2008) Zbl1174.05048MR2402530DOI10.1007/s10587-008-0009-8
  3. Carmichael, R. D., 10.1090/S0002-9904-1910-01892-9, Am. Math. Soc. Bull. 16 (1910), 232-238. (1910) MR1558896DOI10.1090/S0002-9904-1910-01892-9
  4. Chartrand, G., Oellermann, O. R., Applied and Algorithmic Graph Theory, International Series in Pure and Applied Mathematics McGraw-Hill (1993) 1211413. MR1211413
  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). (1974) MR0360322
  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. (2002) Zbl1054.68583MR1962414
  7. Husnine, S. M., Ahmad, U., Somer, L., On symmetries of power digraphs, Util. Math. 85 (2011), 257-271. (2011) MR2840802
  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. (2009) 
  9. Lucheta, C., Miller, E., Reiter, C., Digraphs from powers modulo p , Fibonacci Q. 34 (1996), 226-239. (1996) Zbl0855.05067MR1390409
  10. Somer, L., Křížek, M., 10.1023/B:CMAJ.0000042385.93571.58, Czech. Math. J. 54 (2004), 465-485. (2004) MR2059267DOI10.1023/B:CMAJ.0000042385.93571.58
  11. Somer, L., Křížek, M., 10.1016/j.disc.2005.12.026, Discrete Math. 306 (2006), 2174-2185. (2006) MR2255611DOI10.1016/j.disc.2005.12.026
  12. Somer, L., Křížek, M., On semiregular digraphs of the congruence x k ≡ y ( mod n ) , Commentat. Math. Univ. Carol. 48 (2007), 41-58. (2007) MR2338828
  13. Somer, L., Křížek, M., 10.1016/j.disc.2008.04.009, Discrete Math. 309 (2009), 1999-2009. (2009) MR2510326DOI10.1016/j.disc.2008.04.009
  14. Wilson, B., Power digraphs modulo n , Fibonacci Q. 36 (1998), 229-239. (1998) Zbl0936.05049MR1627384
  15. MATLAB, The language of technical computing (version 7.0.0.19920 (R14)), . 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.