On the Edge Connectivity of k-Distance Graph Products Involving Paths and Cycles.

Abstract

By decomposing the k-distance product G \square_k H of two graphs G and H into the Cartesian product of graph powers, we determine its exact edge connectivity \kappa'. Leveraging this result, we completely formulate edge connectivity for k-distance products of path-path, cycle-cycle, and hybrid path-cycle graph pairs across both degenerate and non-degenerate regimes. Moreover, we observe that the closed-form expressions of edge connectivity for these specific graph families generalize the corresponding results for the standard Cartesian product.