Structural properties of generalized power congruence graphs over sets of moduli

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 $ M_p = \{p^t : t\geq 1, \; p^t < n\} $, where $ p $ is a prime. For $ n \in \mathbb{Z}^{+} $, consider $ V = \{0, 1, \dots, n-1\} $ as the vertex set. We construct a simple, undirected graph $ G(n, k, M_p) $ without loops or multiple edges over $ V $ in which two distinct vertices $ a, b\in V $ are adjacent if $ a^k \equiv b \ (\text{mod }{m}) $ for some $ m\in M_p $ and fixed $ k\in\mathbb{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\text{ 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 $ K_n^{F} $ obtained from a complete graph $ K_n $ by deleting a specified set of edges $ F \subseteq E(K_n) $. When $ p = 5 $, the graph becomes more intricate and depends on $ k\text{ mod }4 $, producing configurations that include both complete components and components $ K_n^{F} $ obtained from a complete graph $ K_n $ by deleting a specified set of edges $ F \subseteq E(K_n) $. In general, for a prime $ p $, the structure of the graph is determined by the residue class of $ k\text{ 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.