On simple graphs arising from exponential congruences
type: Item
instance of: scholarly article
title: On simple graphs arising from exponential congruences
zbMATH Open document ID: 1279.05074
DOI: 10.1155/2012/292895
author: Xianqiang Yang
published in: Journal of Applied Mathematics
publication date: 2012-11-15T00:00:00Z
review text: Summary: We introduce and investigate a new class of graphs arrived from exponential congruences. For each pair of positive integers \(a\) and \(b\), let \(G(n)\) denote the graph for which \(V = \{0, 1, \dots, n - 1\}\) is the set of vertices and there is an edge between \(a\) and \(b\) if the congruence \(a^x \equiv b\pmod n\) is solvable. Let \(n = p^{k_1}_1 p^{k_2}_2 \cdots p^{k_r}_r\) be the prime power factorization of an integer \(n\), where \(p_1 < p_2 < \cdots< p_r\) are distinct primes. The number of nontrivial self-loops of the graph \(G(n)\) has been determined and shown to be equal to \(\Pi^r_{i=1}(\varphi(p^{k_i}_i)+ 1)\). It is shown that the graph \(G(n)\) has \(2^r\) components. Further, it is proved that the component \(\Gamma_p\) of the simple graph \(G(p^2)\) is a tree with root at zero, and if \(n\) is a Fermat's prime, then the component \(\Gamma_{\phi(n)}\) of the simple graph \(G(n)\) is complete.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 11A07
zbMATH DE Number: 6106168
Wikidata QID: Q58906577
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2012/292895
OpenAlex ID: W2134383379
cites work: Some digraphs arising from number theory and remarks on the zero-divisor graph of the ring \(Z_n\)
cites work: Q4936013
cites work: On a Connection of Number Theory with Graph Theory
cites work: Symmetric digraphs from powers modulo \(n\)
cites work: On the symmetric digraphs from powers modulo \(n\)
cites work: Q4350166
cites work: Q3128821
DBLP publication ID: journals/jam/MalikM12
description: scientific article; zbMATH DE number 6106168