Geodesic
On the tree structure of the power digraphs modulo $n$
Czechoslovak Mathematical Journal, Tome 65 (2015) no. 4, pp. 923-945
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-015-0218-x
Classification : 05C05, 05C20, 11A07, 11A15, 68R10
Keywords: congruence; symmetric digraph; fundamental constituent; tree; digraph product; semiregular digraph 
@article{10_1007_s10587_015_0218_x,
     author = {Sawkmie, Amplify and Singh, Madan Mohan},
     title = {On the tree structure of the power digraphs modulo $n$},
     journal = {Czechoslovak Mathematical Journal},
     pages = {923--945},
     year = {2015},
     volume = {65},
     number = {4},
     doi = {10.1007/s10587-015-0218-x},
     mrnumber = {3441326},
     zbl = {06537701},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0218-x/}
}
TY  - JOUR
AU  - Sawkmie, Amplify
AU  - Singh, Madan Mohan
TI  - On the tree structure of the power digraphs modulo $n$
JO  - Czechoslovak Mathematical Journal
PY  - 2015
SP  - 923
EP  - 945
VL  - 65
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0218-x/
DO  - 10.1007/s10587-015-0218-x
LA  - en
ID  - 10_1007_s10587_015_0218_x
ER  - 
%0 Journal Article
%A Sawkmie, Amplify
%A Singh, Madan Mohan
%T On the tree structure of the power digraphs modulo $n$
%J Czechoslovak Mathematical Journal
%D 2015
%P 923-945
%V 65
%N 4
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0218-x/
%R 10.1007/s10587-015-0218-x
%G en
%F 10_1007_s10587_015_0218_x
Sawkmie, Amplify; Singh, Madan Mohan. On the tree structure of the power digraphs modulo $n$. Czechoslovak Mathematical Journal, Tome 65 (2015) no. 4, pp. 923-945. doi: 10.1007/s10587-015-0218-x

[1] Deng, G., Yuan, P.: On the symmetric digraphs from powers modulo $n$. Discrete Math. 312 (2012), 720-728. | DOI | MR | Zbl

[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 | Zbl

[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 | MR | Zbl

[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 | MR

[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

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

Cité par Sources :