Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
congruence; symmetric digraph; fundamental constituent; tree; digraph product; semiregular digraph
congruence; symmetric digraph; fundamental constituent; tree; digraph product; semiregular digraph
Summary:
For any two positive integers $n$ and $k \geq 2$, let $G(n,k)$ be a digraph whose set of vertices is $\{0,1,\ldots ,n-1\}$ and such that there is a directed edge from a vertex $a$ to a vertex $b$ if $a^k \equiv b \pmod n$. Let $n=\prod \nolimits _{i=1}^r p_{i}^{e_{i}}$ be the prime factorization of $n$. Let $P$ be the set of all primes dividing $n$ and let $P_1,P_2 \subseteq P$ be such that $P_1 \cup P_2=P$ and $P_1 \cap P_2= \emptyset $. A fundamental constituent of $G(n,k)$, denoted by $G_{P_2}^{*}(n,k)$, is a subdigraph of $G(n,k)$ induced on the set of vertices which are multiples of $\prod \nolimits _{{p_i} \in P_2}p_i$ and are relatively prime to all primes $q \in P_1$. L. Somer and M. Křížek proved that the trees attached to all cycle vertices in the same fundamental constituent of $G(n,k)$ are isomorphic. In this paper, we characterize all digraphs $G(n,k)$ such that the trees attached to all cycle vertices in different fundamental constituents of $G(n,k)$ are isomorphic. We also provide a necessary and sufficient condition on $G(n,k)$ such that the trees attached to all cycle vertices in $G(n,k)$ are isomorphic.
References:
[1] Deng, G., Yuan, P.: On the symmetric digraphs from powers modulo $n$. Discrete Math. 312 (2012), 720-728. DOI 10.1016/j.disc.2011.11.007 | MR 2872913 | Zbl 1238.05104
[2] Kramer-Miller, J.: Structural properties of power digraphs modulo $n$. Mathematical Sciences Technical Reports (MSTR) (2009), 11 pages, http://scholar.rose-hulman.edu/math\_mstr/11
[3] Křížek, M., Luca, F., Somer, L.: 17 Lectures on Fermat Numbers: From Number Theory to Geometry. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC 9 Springer, New York (2001). MR 1866957 | Zbl 1010.11002
[4] Somer, L., Křížek, M.: The structure of digraphs associated with the congruence $x^k\equiv y\pmod n$. Czech. Math. J. 61 (2011), 337-358. DOI 10.1007/s10587-011-0079-x | MR 2905408 | Zbl 1249.11006
[5] Somer, L., Křížek, M.: On symmetric digraphs of the congruence $x^k\equiv y\pmod n$. Discrete Math. 309 (2009), 1999-2009. DOI 10.1016/j.disc.2008.04.009 | MR 2510326
[6] 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
[7] Wilson, B.: Power digraphs modulo $n$. Fibonacci Q. 36 (1998), 229-239. MR 1627384 | Zbl 0936.05049
Search
Partner of
