The power digraphs of safe primes

Document Type: Research Paper


1 Department of‎ ‎Mathematics‎, ‎University‎ ‎of the Punjab‎, ‎New Campus‎, ‎Lahore‎, ‎Pakistan.

2 Department of Humanities‎ ‎and Sciences‎, ‎National University‎ ‎of Computer and Emerging Sciences(FAST)‎, ‎Lahore Campus‎, ‎Lahore‎, ‎Pakistan.


A power digraph, denoted by $G(n,k)$, is a directed graph with $Z_{n}={0,1,..., n-1}$ as the set of vertices and
$L={(x,y):x^{k}\equiv y~(mod , n)}$ as the edge set, where $n$ and $k$ are any positive integers. In this paper, the structure of $G(2q+1,k)$, where $q$ is a Sophie Germain prime is investigated. The primality tests for the integers of the form $n=2q+1$ are established in terms of the structure of components of $G(n,k)$. The digraphs in which all components look like directed star graphs are completely classified. This work generalizes the results of M. Krizekek, L. Somer, Sophie Germain Little Suns, Math. Slovaca 54(5) (2004), 433-442.


Main Subjects

U. Ahmad and S. Husnine, Characterization of Power Digraphs modulo n, Comment. Math. Univ. Carolin 48 (2011), no. 3, 359--367.

U. Ahmad and S. Husnine, On the Heights of Power Digraphs modulo n, Czechoslovak. Math. J. 62(137) (2012), no. 2, 541--556.

S. M. Husnine, U. Ahmad and L. Somer, On symmetries of Power digraphs, Util. Math 85 (2011) 257--271.

J. Kramer-Miller, Structural properties of power digraphs modulo n, Proceedings of the 2009 Midstates Conference on Undergraduate Research in Computer Science and Mathematics, 40-49, Oberlin, Ohio, 2009.

L. Somer and M. Krizek, On a connection of number theory with graph theory, Czechoslovak Math. J. 54(129) (2004), no. 2, 465--485.

M. Kritzek and L. Somer, Sophie Germain Little Suns, Math. Slovaca 54 (2004), no. 5, 433--442.

L. Somer and M. Kritzek, Structure of digraphs associated with quadratic congruences with composite moduli, Discrete Math. 306 (2006), no. 18, 2174--2185.

L. Somer and M. Kritzek, On semiregular digraphs of the congruence xk =y(mod n), Comment. Math. Univ. Carolin. 48 (2007), no. 1, 41--58.

L. Somer and M. Kritzek, On symmetric digraphs of the congruence xk=y (mod n), Discrete Math. 309 (2009), no. 8, 1999--2009.

B. Wilson, Power digraphs modulo n, Fibonacci Quart. 36 (1996), no. 3, 229--239.