| Abstract [eng] |
In this article, we introduce and study a novel class of graphs called power congruence graphs (PCGs) that are constructed over the sets of moduli of the form Mp = { pt : t ≥ 1, pt < n}, where p is a prime. For n ∈ Z+, consider V = {0, 1, . . ., n − 1} as the vertex set. We construct a simple, undirected graph G(n, k, Mp) without loops or multiple edges over V in which two distinct vertices a, b ∈ V are adjacent if ak ≡ b (mod m) for some m ∈ Mp and fixed k ∈ Z+. We present a comprehensive structural characterization of PGCs for the cases p = 2, 3, 5 and extend the framework to an arbitrary prime p. When p = 2, the graph decomposes into two disjoint complete components for all k. When p = 3, the graph structure is governed by k mod 2; for odd value of k, the graph is a disjoint union of three complete components; and for even value of k, the graph is a disjoint union of one complete component and one component KnF obtained from a complete graph Kn by deleting a specified set of edges F ⊆ E(Kn). When p = 5, the graph becomes more intricate and depends on k mod 4, producing configurations that include both complete components and components KnF obtained from a complete graph Kn by deleting a specified set of edges F ⊆ E(Kn). In general, for a prime p, the structure of the graph is determined by the residue class of k mod (p − 1), giving rise to up to p − 1 distinct structural types. This highlights a systematic transition from simple to increasingly complex graph configurations as the prime modulus increases. Furthermore, we investigate several graph invariants associated with these graphs. This study provides a framework for understanding power congruence-based graph constructions bridging number theory with graph theory. |
