A graph on n vertices is said to admit a prime labeling if we can label its vertices with the first n natural numbers such that any two adjacent vertices have relatively prime labels. Here we extend the idea of prime labeling to the Gaussian integers, which are the complex numbers whose real and imaginary parts are both integers. We begin by defining an order on the Gaussian integers that lie in the first quadrant. Using this ordering, we show that all trees of order at most 72 admit a prime labeling with the Gaussian integers.
Lehmann, Hunter and Park, Andrew
"Prime Labeling of Small Trees with Gaussian Integers,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 17:
1, Article 6.
Available at: https://scholar.rose-hulman.edu/rhumj/vol17/iss1/6