This paper investigates algebraic invariants of edge ideals associated with families of graphs constructed as the strong product of a path or cycle with the complete graph $K_m$, namely ${\mathcal{P}}_{\gamma }=P_{\gamma }⊠K_m$ and ${\mathcal{C}}_{\gamma }=C_{\gamma }⊠K_m$. For an edge ideal $I(\mathbb{G})\subset \mathrm{\Re }$ in a polynomial ring over a field $\mathbb{K}$, we derive explicit combinatorial formulas for key homological and ring-theoretic invariants of the quotient ring $\mathrm{\Re }/I(\mathbb{G})$. These include Castelnuovo-Mumford regularity, depth, Stanley depth, projective dimension, and Krull dimension. Furthermore, we characterize all Cohen–Macaulay graphs in defined families, providing a complete classification where $\mathrm{\Re }/I(\mathbb{G})$ is Cohen–Macaulay.