Symmetry and Structural Analysis of Power Congruence Graphs over a Set of Moduli

In this article, we introduce and investigate a novel class of graphs that are called Power Congruence Graph PCGs, which are defined over the vertex set V ={0,1,2,…,n−1} where two vertices a,b∈V are adjacent if ak≡bk(modm) for some modulus m∈Mp, where Mp={p,p2,…,pt∣pt<n}. We thoroughly characterize the structural features of these graphs, establishing that each PCG decomposes into a union of d+1 complete components, where d=p−1gcd(k,p−1). The component sizes are explicitly given for n, p, and k. This decomposition highlights symmetry patterns in the component arrangement, emphasizing connectedness and structural balance. We derive key graph-theoretic metrics such as degree distribution, size, chromatic number, clique number and domination number. We also compute the adjacency and Laplacian matrices, as well as their spectra and associated graph energies to better understand the structural similarities and differences among PCGs with different exponents and prime moduli. This paper offers a systematic framework for comprehending power congruence based graph constructs, integrating number theory with structural and spectral graph theory and illustrating the natural symmetry that underpins these combinatorial structures.