Gaussian Labeling of Product Graph Is P

This paper explores a novel graph labelling scheme using Gaussian integers applied to Cartesian product graphs. We introduce a prime labelling technique where Gaussian integers, as opposed to traditional natural numbers, are assigned to the graph elements. The primary result is a proof that this labelling is prime for the specified Cartesian product graphs. A significant application of this labelling is demonstrated in its ability to efficiently reveal Hamiltonian paths within the graph structure. Specifically, the Gaussian integer prime labelling provides a direct mechanism for identifying a Hamiltonian path that corresponds to the minimum distance. Furthermore, the chapter includes a comprehensive analysis of the graph's total weight based on this labelling. The study of such Gaussian integer labellings, including magic, anti-magic, and prime variants, is motivated by their potential for groundbreaking applications in coding theory and network design, particularly in the creation of innovative block labelling schemes. Given the widespread utility of Cartesian product graphs across diverse fields like computer science, mathematical chemistry, and biology, the proposed prime labelling with Gaussian integers is posited to offer substantial theoretical and practical advantages.