A prime labeling of a simple finite graph \(G\) is a labeling of the vertices with distinct integers from \(\{1,2, \dots, |G|\}\) such that the labels of any two adjacent vertices are coprime. If \(G\) admits such a labeling, we call \(G\) a prime graph. If the set \(\{1,2, \dots, |G|\}\) is replaced by \(\{k,k+1, \dots, k+|G|-1\}\) in the previous definition, then we call it \(k\)-prime labeling, where \(k\) is a positive integer. Since some graph might be 2-prime labeling but not 3-prime labeling, to avoid ambiguity, we define uniform prime labeling for graphs. Focused on trees, using some very classical number theory results, we show that any star is uniform prime if and only if it has at most 16 vertices. We also prove any tree of order \(n\) with diameter \(n-1\), \(n-2\), \(n-3\), and \(n-4\) are uniform prime. Based on these results and several trees with diameter \(n-5\), we show that any tree with at most 8 vertices (There are 1+1+1+2+3+6+11+23=48 such non-isomorphic trees) are uniform prime. We also verified the uniform primality of several periodically constructed trees. We post some open questions and conjectures which should be essential and interesting by the end of Section 4. For example, we conjecture all the trees with order up to 16 are uniform prime and ask if there exists a tree other than star is not uniform prime.
Graph labeling is a fundamental area in graph theory in which integers (or other labels) are assigned to the vertices, edges, or both of a graph subject to specified conditions. The subject traces its origins to the 1960s, beginning with the work of Alexander Rosa [16], who introduced a hierarchy of labeling-originally called valuations-in 1967 in connection with cyclic decomposition of complete graphs. These ideas were later popularized and further developed by Solomon Golomb, who coined the term graceful labeling for one of the most prominent classes. Since then, graph labeling has grown into a rich and active field with hundreds of distinct labeling schemes.
The importance of graph labeling extends beyond pure combinatorics. It has practical applications in diverse domains, including coding theory (designing error-correcting codes), communication networks (addressing systems and channel assignment), cryptography, radar and missile guidance, astronomy, circuit design, x-ray crystallography, and database management. For instance, certain labelings model non-periodic codes for pulse radar or ensure non-interfering frequency assignments in networks. A comprehensive overview of these applications and the vast literature on labelings can be found in the dynamic survey by Joseph A. Gallian [6] (regularly updated in The Electronic Journal of Combinatorics, latest version as of 2022, https://www.combinatorics.org/files/Surveys/ds6/ds6v25-2022.pdf).
The concept of prime labeling was first introduced by R. J. Entringer [4] in the early 1980s. In this labeling scheme, the adjacency relation in a graph is governed by the coprimality of vertex labels, thereby linking graph-theoretic structure with the distribution of prime factors among integers. The Entringer-Tout Conjecture stands as one of the most significant open problems in graph labeling, asserting that every tree with \(n\) vertices is a prime graph. Proposed by Roger Entringer around 1980 and first appearing in literature via Tout, Dabboucy, and Howalla in 1982. While the conjecture remains unproven for all trees, substantial progress has been made. Verification initially confirmed its validity for small trees up to 15 vertices by Fu and Huang in 1994 [5], and later for trees with up to 50 vertices by Pikhurko in 2007 [10]. A major theoretical breakthrough occurred in 2011 when Haxell, Pikhurko, and Taraz [8] proved that the conjecture holds for all sufficiently large trees. Despite this, a complete proof for all finite trees is still the subject of active research in combinatorial design and number theory. In [5], the authors proved the primility of perfect binary tree and Joseph Chang generalized this to any complete binary tree by using Hall’s marriage theorem [3]. Robertson and Small [15] extended Newman’s conjecture then proved various families of trees are prime, including palm trees, banana trees, binomial trees and certain of spider colonies. On the other hand, Kenigsberg and Levin proved that all the infinite trees are prime in [9].
In 2011, Vaidya and Prajapati introduced the \(k\)-prime labeling. Namely, they use the set \(\{k,k+1,\dots, k+n-1\}\) to replace the set \(\{1,2, \dots, |G|\}\) in the definition of prime labeling. In 2021, Youssef and Omar [18] studied the \(k\)-primality for circle, helm and some other graphs. In 2024, Abughneim and Abughazaleh [1] characterized when a graph up to order 6, or order 7 with \(k(k+1)\) not divisible by 5 is \(k\)-prime. They also investigated the \(k\)-primality of circles. Recently, in [19], we constructed a lot of \(k\)-prime labelings for cycle snake graphs. We also studied the relations among \(k\)-primality when \(1\leq k\leq 5\).
It is obvious that any circle with odd number of vertices is not \(k\)-prime given \(k\) even. Any complete graph with at least 4 vertices is never \(k\) prime for any \(k\). On the other hand, a path is always \(k\)-prime for any \(k\). It is therefore essential to tell these situations apart. In this paper, we introduce the concept, uniform prime labeling (“Complete”, “Total” have been used in literature for something else). Namely, a graph is uniform prime if for every natural number \(k\), there exists a \(k\)-prime labeling. For example, circle \(C_4\) with 4 vertices is 1-prime, 2-prime but not 3-prime. Hence, \(C_4\) is not uniform prime. It is interesting that star graph may not be uniform prime. Based on some very classical results of consecutive integers, we will show that a star is uniform prime if and only if it has at most 16 vertices. Using the size of diameter to classify \(n\) vertices trees, we prove trees are uniform prime if their diameters are no less than \(n-4\). As a consequence, by consider a few more trees with order \(n\) and diameter \(n-5\), we verify the uniform primality of 48 non-isomorphic trees with order up to 8. We also prove several periodically constructed trees are uniform prime. In the end of section 4, we post several open questions and conjectures. We believe these questions and conjectures are essential and interesting.
In the context of a simple graph \(G = (V, E)\), where \(V\) is the set of vertices and \(E\) is the set of edges, \(|V|\) and \(|E|\) are the order and size respectively of \(G\). Several structural concepts are foundational.
A path \(P_n\) is defined as a sequence of distinct vertices \(v_1, v_2, \dots, v_n\) such that \(E=\{\{v_i, v_{i+1}\} \vert 1 \leq i < n\}\). A star \(S_n\) is defined as a set of \(n\) vertices where one central vertex is connected to all the other \(n-1\) vertices, and no other connections exist between those of vertices. A tree is a connected graph that contains no cycles, meaning there is exactly one unique path connecting any two vertices in \(V\).
The metric properties of a graph are often described using distance and diameter. The distance between two vertices \(u\) and \(v\), denoted as \(d(u, v)\), is the length (number of edges) of the shortest path connecting them. Consequently, the diameter of the graph, denoted as \(\text{diam}(G)\), is the greatest distance between any pair of vertices in the graph:
Obviously, a tree \(T_n\) with \(n\geq 2\) vertices is a path if and only if its diameter is \(n-1\) and \(T_n\) is a star if and only if its diameter is \(2\).
Definition 2.1. Let \(G = (V, E)\) be a graph with \(|V| = n\) vertices. A bijection \(f: V \to \{1, 2, \dots, n\}\) is called a prime labeling if for every edge \(\{u,v\} \in E\), the labels assigned to \(u\) and \(v\) are coprime. That is:
If such a function \(f\) exists, \(G\) is called a prime graph.
We modify the definition of \(k\)-prime labeling in [17] as the following:
Definition 2.2. Let \(G = (V, E)\) be a graph with \(|V| = n\) vertices. If there exists a positive integer \(k\) and an injective function \(f_k: V \to \{k, k+1, \dots, k+n-1\}\) such that for every edge \(\{u,v\} \in E\), the labels are coprime:
then we call \(G\) a \(k\)-prime graph. If \(G\) is \(k\)-prime for any positive integer \(k\), then we call \(G\) a uniform prime graph.
Remark 2.3. Note that a standard prime labeling is simply the specific case where \(k=1\). For an uniform prime graph, the injection functions for different \(k\) might be different.
A famous Indian mathematician, S. S. Pillai, investigated the properties of \(n\) consecutive integers [11, 12, 13, 14].
In 1939, Pillai proved the following result:
Lemma 2.4. [11] When \(n\leq 16\), in every set of \(n\) consecutive integers, there is at least one integer which is coprime to all the rest in the set.
Immediately, we have the following:
Corollary 2.5. When \(n\leq 16\), the star \(S_n\) is uniform prime.
Proof. For any \(k\), \(A_k=\{k,k+1,\dots,k+n-1\}\) is a set of \(n\) consecutive integers with \(n\leq 16\). By Lemma 2.4, there is an element \(a_k\) in \(A_k\) which is coprime to the rest in \(A_k\). We chose \(a_k\) to label the center of the star, then we obtain a \(k\)-prime labeling. \(\square\)
Pillai [11] found both \(\{2184,2185,\dots, 2200\}\) (There is a typo in [11], 2210 should be changed to 2200) and \(\{27830, 27831,\dots, 27846\}\) are two sets of 17 consecutive integers, but no number in any set is coprime to all the rest in that set. Hence, we reach the following conclusion since no qualified number can be used to label the center of the star:
The star \(S_{17}\) is neither 2184-prime nor 27830-prime .
Therefore, \(S_{17}\) is not uniform prime. The following result was conjectured by Pillai and proved by Alfred Brauer in 1941.
Lemma 2.6. [2] For every \(n\geq 17\) there exists a sequence of \(n\) consecutive integers such that none of these \(n\) integers is coprime to the product of the others.
Remark 2.7. In Lemma 2.6, let \(A_n\) be the set of \(n\) consecutive integers such that none of these \(n\) integers is coprime to the product of the others. It is clear that \(\pm 1\notin A_n\). Hence, all the consecutive numbers in \(A_n\) will be simultaneously positive or negative. Hence, we always obtain a set \(A_n\) with \(n\) consecutive positive integers such that none of these \(n\) positive integers is coprime to the product of the others. Equivalently, for every number \(a\) in \(A_n\), there is another number \(b\) in \(A_n\), such that \(\gcd(a,b)>1\).
From Remark 2.7, we immediately have:
Corollary 2.8. For any \(n\geq 17\), the star \(S_n\) is not uniform prime.
Proof. Let \(A_n=\{k_n, k_n+1,\dots,k_n+n-1\}\) be the set in Remark 2.7, then \(S_n\) is not \(k_n\)-prime since no one in \(A_n\) can be assigned to the center, hence, not uniform prime. \(\square\)
Combine the above two corollaries, we obtain the following result.
Theorem 2.9. A star \(S_n\) is uniform prime if and only if \(n\leq 16\).
We have described the uniform primality of tree with minimal diameter 2 when the tree has at least 3 vertices. In the next section, we will verify the uniform primality of trees with diameter \(n-1\), \(n-2\), \(n-3\) and \(n-4\). We list some simple elementary number theory facts below. They may not be independent to each other, namely, some of them may be implied by the others. These facts will be frequently used in this paper later.
Lemma 2.10. Let \(a\), \(b\) and \(m\geq 1\) be any integer,
A tree of order \(n\) with diameter \(n-1\) must be the path \(P_n\), clearly, it is uniform prime.
A tree with less than 4 vertices must be a path and hence uniform prime. When \(n\geq 4\), we have
Theorem 3.1. Any tree with \(n\geq 4\) vertices and diameter \(n-2\) is uniform prime.
Proof. Any tree with \(n\geq 4\) vertices and diameter \(n-2\) must be graph formed by a path \(P_{n-1}\) and exactly one of its internal vertex is connected to a new vertex. We draw such tree below:
We construct the label function \(f\) as below:
Following the natural order, we simply assign \(k\) to \(v_1\), \(k+1\) to \(v_2\),…, \(k+i-2\) to \(v_{i-1}\). If \(k+i-1\) is odd, then \(f(v_i)=k+i-1\), \(f(v_n)=k+i\) \(f(v_{i+1})=k+i+1\),…, \(f(v_{n-1})=k+n-1\). If \(k+i-1\) is even, then we switch the value of \(f(v_i)\) and \(f(v_n)\) in the above labeling. It is easy to check this function \(f\) does not violate coprime requirement. \(\square\)
Please note, the restriction \(2\leq i\leq n-2\) guarantees the diameter is \(n-2\). But we do not need it in the above proof. In other words, the tree is still uniform prime if \(i=1\) or \(i=n-1\). Similar things are also true in the rest of this paper.
For any subset of the vertices set of a path, each vertex in the subset is connected to a different new vertex. We repeatedly use the above method, then the obtained new graph is still uniform prime, we formally write it below for future application.
Theorem 3.2. Given path \(P_m\), \(V(P_m)=\{v_1,v_2,…,v_m\}\), \(E(P_m)=\{\{v_i,v_{i+1}\}| 1\leq i<m\}\), let \(\{i_1, i_2,…, i_k\}\) be any subset of \(\{1,2,…,m\}\). Let \(\{u_1, u_2,…, u_k\}\) be a set of new vertices, we connect \(v_{i_t}\) to \(u_t\) for \(t=1,2,…,k\), then the new graph is uniform prime.
Theorem 3.3. Any tree with order \(n\) and diameter \(n-3\) is uniform prime.
Proof. Any tree with order \(n\geq 5\) and diameter \(n-3\) can be obtained by connecting two different new vertices to the internal vertices of a path \(P_{n-2}\). It is clear that there are three cases:
Case 1. These two new vertices are connected to two different internal vertices of \(P_{n-2}\). This is a special case of Theorem 3.2.
Case 2. Both two new vertices are connected to the same internal vertex \(v_i\) of \(P_{n-2}\). We sketch it below.
We label Figure 2 below:
Case 2.1. \(k+i \equiv 0,2 \pmod {6}\).
Case 2.2. \(k+i \equiv 1,3,5 \pmod {6}\). Switch \(k+i\) with \(k+i-1\) in Figure 3.
Case 2.3. \(k+i \equiv4 \pmod {6}\). Switch \(k+i-1\) with \(k+i+1\) in Figure 3.
It is easy to check that all the labelings satisfy the coprime requirements by Lemma 2.10.
Case 3. The first new vertex is connected with one internal vertex of \(P_{n-2}\), then the second new vertex is connected with the first new vertex.
Case 3.1. \(k+i \equiv 0,2 \pmod {3}\). We do the labeling in the graph directly.
Case 3.2. \(k+i \equiv 1 \pmod {3}\). Switch \(k+i-1\) with \(k+i+1\) in Case 3.1, Figure 4. \(\square\)
Remark 3.4. In the above proof, once the graph is given, then the \(i\) is a fixed number although \(3\leq i\leq n-4\). Of course, the labeling depends on \(i\). Therefore, when \(k+i\) runs all the remainders of modulo 3 or modulo 6, so does \(k\).
Theorem 3.5. Any tree with order \(n\) and diameter \(n-4\) is uniform prime.
Proof. Basically, three new vertices will be connected to the internal vertices of the path \(P_{n-3}\). We have three cases, first, three different internal vertices of \(P_{n-3}\) will be connected to some new vertices. Second, two internal vertices of \(P_{n-3}\) will be connected to some new vertices. Finally, only one internal vertices of \(P_{n-3}\) will be connected to new vertices. Each case might be divided into more sub-cases.
Case I. Chose any three internal vertices \(P_{n-3}\), each will be connected to a new vertex. This is a special case of Theorem 3.2.
Case II. Let \(v_i\) and \(v_j\) (\(i< j\)) be two internal vertices of \(P_{n-3}\). \(E(P_{n-3})=\{\{v_k,v_{k+1}\} | k=1,2,..,n-4\}\). Without loss of generality, we assume \(v_i\) will be connected with 2 new vertices and \(v_j\) will be connected with one new vertex. Otherwise, when we look the graph from the back of the paper, the original “right” becomes “left” now. Hence, there are two sub-cases. First, both new vertices \(A\) and \(B\) are connected to \(v_i\). Second, the first new vertex \(A\) is connected to \(v_i\), then the second new vertex \(B\) is connected to the first new vertex \(A\).
Case II.1. See Figure 5.
If \(j\geq i+2\), then we first use the labeling of Case 2 in Theorem 3.3 to label vertices \(\{v_1,…,v_i,A,B\}\), the label of \(v_{i+1}\) is always \(k+ i+2\). Now, we use the method of Theorem 3.1 to label and we are done.
We deal with \(j=i+1\) now. We must handle the connection of two labels.
Again, we first use the labeling of Case 2 in Theorem 3.3 to label vertices \(\{v_1,…,v_i,A,B\}\).
In Case 2.1 of Theorem 3.3, \(k+i+2\) is even number, so we use \(k+i+2\) to label \(C\) and use \(k+i+3\) to label \(v_{i+1}\)(\(=v_j\)), it is clear that \(\gcd(k+i-1, k+i+3)=1\).
In Case 2.2 of Theorem 3.3, \(k+i+2\) is odd number, we use \(k+i+3\) to label \(C\) and use \(k+i+2\) to label \(v_{i+1}\)(\(=v_j\)), it is clear that \(\gcd(k+i, k+i+2)=1\).
In Case 2.3 of Theorem 3.3, \(k+i+2\) is even number, so we use \(k+i+2\) to label \(C\) and use \(k+i+3\) to label \(v_{i+1}\)(\(=v_j\)), it is clear \(\gcd(k+i+1, k+i+3)=1\).
Case II.2. See the graph Figure 6.
We only consider the case \(j=i+1\) as before. We have three sub-cases.
Case II.2.1. \(k+i\equiv 3,5 \pmod{6}\). We do the labeling in Figure 7.
Case II.2.2. \(k+i\equiv 1 \pmod{6}\). We switch \(k+i-1\) with \(k+i+1\) in Figure 7.
Case II.2.3. \(k+i\equiv 0, 2, 4 \pmod{6}\). We switch \(k+i+2\) with \(k+i+3\) in Figure 7.
Case III. All the 3 new vertices will be connected to \(v_i\). There are four sub-cases. Suppose \(A\), \(B\) and \(C\) are three new vertices. In the first case, all the three new vertices are directly connected to \(v_i\) respectively. In the second case, both \(A\) and \(C\) are connected to \(V_i\), then \(B\) is connected to \(A\). In the third case, \(A\) is connected to \(v_i\), then both \(B\) and \(C\) are connected to \(A\). Finally, \(A\) is connected to \(V_i\), \(B\) connected to \(A\) and \(C\) connected to \(B\).
Case III.1. See Figure 8. We consider four sub-cases.
Case III.1.1. \(k+i \equiv 0, 2 \pmod {6}\). We label the tree in Figure 9.
Case III.1.2. \(k+i \equiv 1, 5 \pmod {6}\). Switch \(k+i-1\) with \(k+i\) in Figure 9.
Case III.1.3. \(k+i \equiv 4 \pmod {6}\). Switch \(k+i-1\) with \(k+i+1\) in Figure 9.
Case III.1.4. \(k+i \equiv 3 \pmod {6}\). Switch \(k+i-1\) with \(k+i+2\) in Figure 9.
Case III.2. See Figure 10. We consider three subcases.
Case III.2.1. \(k+i\) is even. We do the labeling in Figure 11.
Case III.2.2. \(k+i\equiv 3,5 \pmod {6}\). We do the labeling in Figure 12.
Case III.2.3. \(k+i\equiv 1 \pmod {6}\). We do the labeling in Figure 13.
Case III.3. See Figure 14.
Case III.3.1. \(k+i\) is even, we do labeling in Figure 15.
Case III.3.2. \(k+i\) is odd, we do labeling in Figure 16.
Case III.4. See Figure 17.
We do the labeling in Figure 18 when \(k+i\) is even:
We do the labeling in Figure 19 when \(k+i\) is odd:
\(\square\)
One can continue the line above, to determine the uniform primality of trees of order \(n\) and diameter \(n-5\). Basically, by adding 4 new vertices to the internal vertices of path \(P_{n-4}\). Number “4″ can be written as the following partitions: \(\{4\}\); \(\{3, 1\}\); \(\{2, 2\}\) \(\{2,1,1\}\), \(\{1,2,1\}\) (order sometimes matters if there are more than 3 parts). In each case, there will be many more sub-cases. Although we believe this is doable, the complexity will increase exponentially. In this section, we will prove all the trees of order up to 8 are uniform prime. One can find the figures of all the trees of order up to 10 in the book of F. Harary [7]. Based on the results in Section 3 and Theorem 2.9, one can check all the trees of order up to 7 are uniform prime. For tree with order 8, there are 23 non-isomorphic such trees. Nineteen of them with diameter at least 4 (\(=8-4\)) are uniform prime. One with diameter 2, actually, star \(S_8\) is uniform prime by Theorem 2.9. There are three trees of order 8 with diameter 3 (=8-5) not included in Section 3. In the following, we will prove these three trees are uniform prime. In fact, we will prove three trees with order \(n\) (instead of order 8) are uniform prime.
Theorem 4.1. The following three graphs are uniform prime.
Proof. For Figure 20, if \(j\geq i+2\), we combine the labeling of Figure 8 and Theorem 3.1, then we are done. So, we only need to consider \(j=i+1\). We draw the labeled tree in 4 cases in Figure 23, 24, 25, and 26.
Now we do the uniform prime labeling for Figure 21, as before, we only consider the case \(j=i+1\). We label it in two different cases below:
We label Figure 22 below: There are 5 cases (Figure 29–33). Please note that \(k+i\equiv 2 \pmod{6}\) if and only if \(k+i\equiv 2, 8, 14, 20, 26 \pmod{30}\) since 30 is a multiple of 6. This case has been divided into two sub-cases: namely, \(k+i\equiv 26 \pmod{30}\) and \(k+i\equiv 2, 8, 14, 20 \pmod{30}\).
\(\square\)
The number of trees of order from 1 to 16 are respectively 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, 7741, 19320 (https://oeis.org/A000055). One can check all the trees of order 8 in [7] must be some one in the previous theorems. In summary, we have
Theorem 4.2. All the \(48\) trees with order up to \(8\) are uniform prime.
When diameter is 2, the stars with order at least 17 are not uniform prime. If two trees have the same order, it seems the one with longer diameter have greater probability to be uniform prime since when the vertices are too dense, even the proof takes more cases.
We have the following open questions and conjectures.
1. Are all the trees with order up to 16 uniform prime? We guess the answer is yes.
2. Is there any tree other than star not uniform prime? We guess the answer is yes.
3. We guess there exists a number \(\delta(n)\) for any integer \(n\geq 17\) such that any tree \(T\) with order \(n\) and diameter \(d\) will be uniform prime if \(d\geq \delta(n)\) and at least one tree of order \(n\) will be not uniform prime if \(d<\delta(n)\). In Section 3, we have proved \(\delta(n)\leq n-4\). If the answer of the second question is no, then \(\delta(n)=3\) for any \(n\geq 17\) by Theorem 2.9. We call \(\delta(n)\) the uniform prime diameter threshold value of trees with order \(n\).
4. For any \(n\geq 17\) we have \(3\leq \delta(n)\leq n-4\). An interesting and doable question is to improve the upper bound of \(\delta(n)\).
5. We conjecture \(\delta (n)\leq \delta(n+1)\), namely, the sequence \(\delta (n)\) is non-decreasing.
In this section, for every vertex of the path \(P_n\), we connect \(m\) new vertices to it. Then we get a tree denoted by \(T_n^m\). In other words, for \(n\) copies of star \(S_{m+1}\), we connect each center of these stars one by one to obtain \(T_n^m\) (See Figure 34). We will prove \(T_n^m\) are uniform prime for any \(n\) but \(m\in\{1,2,3,4,5\}\).
We know \(T_n^1\) is uniform prime by Theorem 3.2.
For \(m=2\), we have
Theorem 5.1. For any positive integer \(n\), the tree \(T_n^2\) is uniform prime.
Proof. Let \(I_i=\{k+3i-j|j=1,2,3\}\), \(i=1,2,\dots, n\). Obviously, \(|I_i|=3\), \(|T_n^2|=3n\) and \(\bigcup_{i=1}^nI_i=\{k,k+1,\dots,k+3n-1\}\). We use \(I_i\) to label the \(i\)-th star of \(T_n^2\). We need to find a number in \(I_i=\{k+3i-3, k+3i-2, k+3i-1\}\) and this number is coprime to the rest. We assign this number to \(v_i\). If we use \(f\) to stand for this labeling function, then \(f\) must satisfy \(\gcd (f(v_i),f(v_{i+1}))=1\) for \(i=1,2,\dots,n-1\).
Case 1. \(k\equiv 0,1\pmod{3}\).
Let \(f(v_i)=k+3i-2\), \(i=1,2,\dots, n\). It is routine to check that \(f\) satisfy all the coprime requirements by Lemma 2.10.
Case 2. \(k\equiv 2 \pmod{6}\).
Let
First it is easy to check \(f(v_i)\) is coprime to the other two numbers in \(I_i\).
Suppose \(i\) is odd, then \(i-1\) and \(i+1\) are even. Hence, \(f(v_i)=k+3i-2\), \(f(v_{i-1})=k+3(i-1)-3=k+3i-6\) and \(f(v_{i+1})=k+3(i+1)-3=k+3i\).
We obtain \(\gcd(f(v_{i-1}),f(v_i))=\gcd(k+3i-6,k+3i-2)=1\) and \(\gcd(f(v_{i}),f(v_{i+1}))=\gcd(k+3i-2,k+3i)=1\) by Lemma 2.10.
Case 3. \(k\equiv 5 \pmod{6}\).
Let
First it is easy to check \(f(v_i)\) is coprime to the other two numbers in \(I_i\).
Suppose \(i\) is odd, then \(i-1\) and \(i+1\) are even. Hence, \(f(v_i)=k+3i-1\), \(f(v_{i-1})=k+3(i-1)-2=k+3i-5\) and \(f(v_{i+1})=k+3(i+1)-2=k+3i+1\).
We obtain \(\gcd(f(v_{i-1}),f(v_i))=\gcd(k+3i-5,k+3i-1)=1\) and \(\gcd(f(v_{i}),f(v_{i+1}))=\gcd(k+3i-1,k+3i+1)=1\) by Lemma 2.10. \(\square\)
For \(m=3\), we have
Theorem 5.2. For any positive integer \(n\), the tree \(T_n^3\) is uniform prime.
Proof. Let \(I_i=\{k+4i-j|j=1,2,3,4\}\), \(i=1,2,\dots, n\). Obviously, \(|I_i|=4\), \(|T_n^3|=4n\) and \(\bigcup_{i=1}^nI_i=\{k,k+1,\dots,k+4n-1\}\). We use \(I_i\) to label the \(i\)-th star of \(T_n^3\). We need to find a number in \(I_i=\{k+4i-4, k+4i-3, k+4i-2, k+4i-1\}\) and this number is coprime to the rest. We assign this number to \(v_i\). If we use \(f\) to stand for this labeling function, then \(f\) must satisfy \(\gcd (f(v_i),f(v_{i+1}))=1\) for \(i=1,2,\dots,n-1\).
Case 1. \(k\) is odd.
Let \(f(v_i)=k+4i-2\), \(i=1,2,\dots, n\). It is routine to check that \(f\) satisfy all the coprime requirements by Lemma 2.10.
Case 2. \(k\) is even.
Let \(f(v_i)=k+4i-3\), \(i=1,2,\dots, n\). \(\square\)
For \(m=4\), we have
Theorem 5.3. For any positive integer \(n\), the tree \(T_n^4\) is uniform prime.
Proof. Let \(I_i=\{k+5i-j|j=1,2,3,4,5\}\), \(i=1,2,\dots, n\). Obviously, \(|I_i|=5\), \(|T_n^4|=5n\) and \(\bigcup_{i=1}^nI_i=\{k,k+1,\dots,k+5n-1\}\). We use \(I_i\) to label the \(i\)-th star of \(T_n^4\). We need to find a number in \(I_i=\{k+5i-5, k+5i-4, k+5i-3, k+5i-2, k+5i-1\}\) and this number is coprime to the rest. We assign this number to \(v_i\). If we use \(f\) to stand for this labeling function, then \(f\) must satisfy \(\gcd (f(v_i),f(v_{i+1}))=1\) for \(i=1,2,\dots,n-1\).
Case 1. \(k\) is odd.
Let
Please note, if \(3\mid k+5i-4\), then \(3\nmid k+5i-2\). Use Lemma 2.10, we can easily check that \(f(v_i)\) is coprime to the rest in \(I_i\).
Suppose \(i\) is even, then both \(i-1\) and \(i+1\) are odd, we will show that both \(\gcd (f(v_{i-1}), f(v_{i}))=1\) and \(\gcd (f(v_i),f(v_{i+1}))=1\). Hence, we finish the proof of this case.
We have
We also have
Case 2. \(k\) is even.
Let
Please note, if \(3\mid k+5i-4\), then \(3\nmid k+5i-2\). Use Lemma 2.10, we can easily check that \(f(v_i)\) is coprime to the rest in \(I_i\).
Suppose \(i\) is even, then both \(i-1\) and \(i+1\) are odd, we will show that both \(\gcd (f(v_{i-1}), f(v_{i}))=1\) and \(\gcd (f(v_i),f(v_{i+1}))=1\). Hence, we finish the proof of this case.
We have
We also have
In the last step, we have \(3\nmid k+5i\pm3\) since \(3\mid k+5i+1\). \(\square\)
For \(m=5\), we have
Theorem 5.4. For any positive integer \(n\), the tree \(T_n^5\) is uniform prime.
Proof. Let \(I_i=\{k+6i-j|j=1,2,3,4,5,6\}\), \(i=1,2,\dots, n\). Obviously, \(|I_i|=6\), \(|T_n^5|=6n\) and \(\bigcup_{i=1}^nI_i=\{k,k+1,\dots,k+6n-1\}\). We use \(I_i\) to label the \(i\)-th star of \(T_n^5\). We need to find a number in \(I_i=\{k+6i-6, k+6i-5, k+6i-4, k+6i-3, k+6i-2, k+6i-1\}\) and this number is coprime to the rest. We assign this number to \(v_i\). If we use \(f\) to stand for this labeling function, then \(f\) must satisfy \(\gcd (f(v_i),f(v_{i+1}))=1\) for \(i=1,2,\dots,n-1\).
Case 1. \(k\equiv 1, 3 \pmod{6}\). Let \(f(v_i)=k+6i-2\), \(i=1,2,\dots, n\). It is routine to check that \(f\) satisfy all the coprime requirements by Lemma 2.10.
Case 2. \(k\equiv 2, 4 \pmod{6}\). Let \(f(v_i)=k+6i-3\), \(i=1,2,\dots, n\).
Case 3. \(k\equiv 5 \pmod{6}\). Let \(f(v_i)=k+6i-4\), \(i=1,2,\dots, n\).
Case 4. \(k\equiv 0 \pmod{6}\). Let \(f(v_i)=k+6i-5\), \(i=1,2,\dots, n\). \(\square\)
In this paper we define a new concept \(\textit{Uniform Prime labeling}\), we prove any trees with diameter at least \(n-4\) are uniform prime. We also prove several trees which are periodically constructed are uniform prime. As a consequence, in addition to a few more uniform prime trees with diameter \(n-5\), we show all the trees with order up to 8 are uniform prime by classifying the trees into different groups with fixed diameter. It is interesting that there exists trees (stars) which are not uniform prime. But this is natural since uniform prime labeling has much more restrictions than traditional prime labeling. In Section 3 and 4, we label the tree directly by “writing” the number on the vertex in the graph. In Section 5, we use mathematical formula to describe the labeling function. We propose several open questions by the end of Section 4 and we hope these questions will stimulate further research in graph theory, number theory, and computer science.