دانلود رایگان مقاله برچسب اصلی خانواده درختان با اعداد صحیح گاوسی

Abstract

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 several families of trees admit a prime labeling with the Gaussian integers.

4. Future work and open problems

We conclude with a few open problems and directions for future research. (1) A binary tree is a rooted tree in which each node has at most two children. There are many special classes of binary trees, such as full binary trees, perfect binary trees, or complete binary trees. Investigate Gaussian prime labelings of these families of trees. (2) Investigate Gaussian prime labelings of general (n, k)-firecracker trees. (3) Investigate Gaussian prime labelings of families of non-tree graphs. (4) In a recent paper [4], the second and third authors showed that trees on at most 73 vertices admit Gaussian prime labelings. The approach outlined in that paper pushed the limits of what one could possibly hope to do by hand. Is it possible to computationally verify the conjecture for trees on more vertices? (5) Investigate other inherent properties of the spiral ordering on the Gaussian integers. In what ways is it similar to the properties of the order on the natural numbers and in what ways is it different?