© Wuhan University 2025

0 Introduction

Graph labeling is one of the most important research problems in graph theory, and the coprime labeling of graph is one of the hottest issues, which has attracted the attention of many mathematicians. Graph labeling is the assignment of integers to the vertices, edges, or both, subject to certain conditions. Graph labelings were first introduced in the middle of 1960s. In the intervening 60 years, over 200 graph labeling techniques have been studied in over 2 000 papers^[1]. A graph $G$with vertices set $V$ is said to have coprime labeling if its vertices are labeled with distinct integers $\mathrm{1,2},\cdots ,|V|$such that for each edge $xy$the labels assigned to $x$and $y$are relatively prime. If such a labeling exists, then $G$is said to be prime. Prime graphs have been of interest since the 1980s and were popularized by the Entringer-Tout Tree Conjecture which states that all trees are prime. In 1994, Fu and Huang^[2] showed that all trees of order up to 15 are prime. In 2007, Pikhurko^[3] proved that all trees of order up to 50 are prime. The classes of trees known to have prime labelings are paths, stars, caterpillars, complete binary trees, spiders, olive trees, palm trees, banana trees, binomial trees and so on^[4]. In 2011, Haxell et al^[5] proved that all large trees are prime. In this paper, we will try to generalize the coprime labelings of graph to hypergraph.

Hypergraphs, an extension of traditional graphs, have found wide applications in various fields. Hypergraph labeling, similar to graph labeling, is a crucial concept with significant implications. It provides a way to assign integers to vertices, edges, or both in a hypergraph, which is not only fundamental for understanding the structural properties of hypergraphs but also serves as a powerful tool in solving practical problems. By carefully defining and analyzing hypergraph labelings, mathematicians can gain insights into the internal structure of hypergraphs, and this understanding can be applied to optimize algorithms, design efficient communication networks, and analyze complex systems. Like the coprime labeling of graphs, we expect that the coprime labelings of hypergraphs will have more significant applications and theoretical value.

1 Motivation and Main Results

Note that a hypergraph is a graph in which generalized edges (called hyperedges) may connect more than two vertices. Formally, a hypergraph $H$is a pair $H=(X,E)$, where $X$is a set of elements, called vertices, and $E$is a set of non-empty subsets of $X$called hyperedges. Naturally, the coprime labelings of a graph can be generalized to the hypergraph. A hypergraph of order $n$is prime if its vertices are labeled with distinct integers $\mathrm{1,2},\cdots ,n$,so that there is at least one number in a hyperedge, which is coprime to the rest numbers in that hyperedge. Namely, let $H=(X,E)$be a hypergraph with $m$hyperedg:

$E_{\mathrm{1}}=\left\{e_{\mathrm{11}},e_{\mathrm{12}},\cdots ,e_{\mathrm{1}{k}_{\mathrm{1}}}\right\},\cdots ,[Em=\{e\mathrm{11},e\mathrm{12},\cdots ,e\mathrm{1}km\}]$

and let $\mathit{X}={\mathit{E}}_{\mathrm{1}}\bigcup {\mathit{E}}_{\mathrm{2}}\bigcup \dots \bigcup {\mathit{E}}_{\mathit{m}}$ and $\left|\mathit{X}\right|=\mathit{n}$. If its all vertices ${\mathit{e}}_{\mathit{i}\mathit{j}}$ are labeled with distinct integers $\mathrm{1,2},\cdots ,\mathit{n}$ so that for$\forall \mathrm{1}\le \mathit{i}\le \mathit{m}$, there is at least ${\mathit{e}}_{\mathit{i}\mathit{j}}(\mathrm{1}\le \mathit{j}\le {\mathit{k}}_{\mathit{j}})$ in ${\mathit{E}}_{\mathit{i}}=\{{\mathit{e}}_{\mathit{i}\mathrm{1}},{\mathit{e}}_{\mathit{i}\mathrm{2}},\cdots ,{\mathit{e}}_{\mathit{i}{\mathit{k}}_{\mathit{i}}}\}$satisfying$\mathbf{g}\mathbf{c}\mathbf{d}({\mathit{e}}_{\mathit{i}\mathit{j}},{\mathit{e}}_{\mathit{i}\mathit{r}})=\mathrm{1}$$(\mathrm{1}\le \mathit{r}\ne \mathit{j}\le {\mathit{k}}_{\mathit{i}})$, then we call $\mathit{H}=(\mathit{X},\mathit{E})$ a prime hypergraph. Here we must point out that each hyperedge includes at least two vertices. We do not consider isolated points or single cycles because they must satisfy the condition of being coprime. Thus, the coprime labeling of hypergraphs is essentially a number theoretical problem. A hypergraph is linear if any two hyperedges have at most one common vertex. Clearly, a tree is a special linear hypergraph. The result by Haxell, Pikhurko and Taraz^[5] shows that all large trees are prime hypergraphs. Here, we will prove that certain types of linear hypergraphs are prime. However, it remains unknown whether all linear hypergraphs are prime hypergraphs. We present the following theorems.

Theorem 1   If any two hyperedges of a linear hypergraph $H=(X,E)$ have no common vertex, then $H=(X,E)$ is a prime hypergraph.

Theorem 2   If a linear hypergraph $H=(X,E)$ has $n$hyperedges and each hyperedge has $n$vertices, then when $n>\mathrm{43}$, $H=(X,E)$ is a prime hypergraph.

2 Proofs of Main Results

Lemma 1   (Coprime mapping theorem by Pomerance and Selfridge^[6]) If $n$is a positive integer and$I$is a set of $n$consecutive integers, then there is a bijection$f$:$\{\mathrm{1,2},\cdots ,n\}\to I$ such that $\mathrm{g}\mathrm{c}\mathrm{d}(i,f\left(i\right))=\mathrm{1}$ for $\mathrm{1}\le i\le n$. We call such $f$a coprime mapping.

Proof of Theorem 1   Suppose that the linear hypergraph $H=(X,E)$ has $n$hyperedges and the numbers of vertices in each hyperedge are $k_{\mathrm{1}},k_{\mathrm{2}},\cdots ,k_n$, respectively. Without losing generality, we assume that $k_{\mathrm{1}}\ge k_{\mathrm{2}}\ge$$\cdots \ge k_n$. Suppose that vertices in the i-th hyperedge are labeled with distinct integers $v_{i\mathrm{1}},v_{i\mathrm{2}},\cdots ,e_{i{k}_i}$. Note that any two hyperedges have no common vertex. Therefore, we obtain an echelon form:

$\left(\begin{array}{ccc}{v}_{\mathrm{11}}& \dots & v_{\mathrm{1}{k}_{\mathrm{1}}}\\ ⋮& \dots & ⋮\\ v_{n\mathrm{1}}& \dots & v_{n{k}_n}\end{array}\right)$

Firstly, we identify the first column: $v_{i\mathrm{1}}=i$, $\mathrm{1}\le$$i\le n$. So, $v_{\mathrm{11}},v_{\mathrm{21}},\cdots ,e_{n\mathrm{1}}$ are exactly the consecutive positive integers: $\mathrm{1,2},\cdots ,n$. Secondly, we consider how to label the second column $v_{i\mathrm{2}}$. By Lemma 1, there is a coprime mapping between $\{\mathrm{1,2},\cdots ,n\}$and $\{n+\mathrm{1},n+\mathrm{2},\cdots ,n+n\}$. Let $v_{\mathrm{12}},v_{\mathrm{22}},\cdots ,e_{n\mathrm{2}}$ be the permutation of $n+\mathrm{1},n+\mathrm{2},\cdots ,n+n$such that$\mathrm{g}\mathrm{c}\mathrm{d}(i,v_{i\mathrm{2}})=\mathrm{1}$($\mathrm{1}\le i\le n$). Therefore, the echelon form becomes the following shape:

$\left(\begin{array}{cccc}\mathrm{1}& v_{\mathrm{12}}& \dots & v_{\mathrm{1}{k}_{\mathrm{1}}}\\ \mathrm{2}& v_{\mathrm{22}}& \dots & ⋮\\ ⋮& ⋮& \dots & ⋮\\ n& v_{n\mathrm{2}}& \dots & v_{n{k}_n}\end{array}\right).$

Thirdly, we consider how to label the third column $v_{i\mathrm{3}}$. If the third column still has $n$elements, then by Lemma 1, there is a coprime mapping between $\{\mathrm{1,2},\cdots ,n\}$ and $\{\mathrm{2}n+\mathrm{1,2}n+\mathrm{2},\cdots ,\mathrm{2}n+n\}$. If there are only $t$elements in the third column and $t<n$, then by Lemma 1, there is a coprime mapping between $\{\mathrm{1,2},\cdots ,t\}$and $\{\mathrm{2}n+\mathrm{1,2}n+\mathrm{2},\cdots ,\mathrm{2}n+t\}$. Let $v_{\mathrm{13}},v_{\mathrm{23}},\cdots ,e_{t\mathrm{3}}$ be the permutation of $\mathrm{2}n+\mathrm{1,2}n+\mathrm{2},\cdots ,\mathrm{2}n+t$such that $\mathrm{g}\mathrm{c}\mathrm{d}(i,v_{i\mathrm{3}})=\mathrm{1}$, $\mathrm{1}\le i\le t$. Therefore, the echelon form becomes the possible shape:

$\left(\begin{array}{ccccc}\mathrm{1}& v_{\mathrm{12}}& v_{\mathrm{13}}& \dots & v_{\mathrm{1}{k}_{\mathrm{1}}}\\ \mathrm{2}& v_{\mathrm{22}}& v_{\mathrm{23}}& \dots & ⋮\\ ⋮& ⋮& ⋮& \dots & ⋮\\ t& v_{t\mathrm{2}}& v_{t\mathrm{3}}& \dots & ⋮\\ ⋮& ⋮& ⋮& \dots & ⋮\\ n& v_{n\mathrm{2}}& v_{n\mathrm{3}}& \dots & v_{n{k}_n}\end{array}\right)$

Note that one is coprime to any natural number. Therefore, one can repeat this process and use the coprime mapping theorem repeatedly until all vertices are labeled such that $\mathrm{g}\mathrm{c}\mathrm{d}(i,v_{ij})=\mathrm{1}$ with $j\ne \mathrm{1}$. Therefore, $H=(X,E)$ is a prime hypergraph and the proof is complete.

Lemma 2   (Rosser-Schoenfeld's inequality^[7]) For$x\ge \mathrm{20.5}$,$\pi \left(\mathrm{2}x\right)-\pi \left(x\right)>\mathrm{0.6}x/\mathrm{l}\mathrm{n}x$, where$\pi \left(x\right)$ is the number of prime numbers which are less than or equal to $x$.$$

Proof of Theorem 2   If a linear hypergraph $H=(X,E)$ has $n$hyperedges, and each hyperedge has $n$vertices, then every hyperedge of $H=(X,E)$ has a vertex, which does not belong to any other hyperedges. Denote these vertices by $v_{\mathrm{11}},v_{\mathrm{22}},\cdots ,v_{nn}$. Thus, a possible coprime labeling of the hypergraph $H=(X,E)$ is represented by the following square array:

$\left(\begin{array}{cccc}{v}_{\mathrm{11}}& \dots & \dots & \dots \\ ⋮& v_{\mathrm{22}}& \dots & ⋮\\ ⋮& \dots & \dots & ⋮\\ \dots & \dots & \dots & v_{nn}\end{array}\right)$

Suppose that the linear hypergraph $H=(X,E)$ has x vertices. Clearly, we have $n^{\mathrm{2}}>x>n(n+\mathrm{1})/\mathrm{2}$. Note that one is coprime to any other integers, and any prime between $x/\mathrm{2}$and $x$is coprime to the rest numbers of the square array. Therefore, in order to prove that the theorem holds, we only need to prove that $\pi \left(x\right)-\pi \left(x/\mathrm{2}\right)>n-\mathrm{1}$. By Lemma 2, we have that for $x>\mathrm{40}$,$\pi \left(x\right)-\pi \left(x/\mathrm{2}\right)>\mathrm{0.6}(x/\mathrm{2})/\mathrm{l}\mathrm{n}(x/\mathrm{2})$. Since$n^{\mathrm{2}}>x>n(n+\mathrm{1})/\mathrm{2}$, hence $\pi \left(x\right)-\pi \left(x/\mathrm{2}\right)>\mathrm{0.15}n(n+\mathrm{1})/(\mathrm{l}\mathrm{n}{n}^{\mathrm{2}}-\mathrm{l}\mathrm{n}\mathrm{2})$. Furthermore, for $n>\mathrm{40}$, $\mathrm{0.15}n(n+\mathrm{1})/(\mathrm{l}\mathrm{n}{n}^{\mathrm{2}}-\mathrm{l}\mathrm{n}\mathrm{2})>n-\mathrm{1}$. Thus $\pi \left(x\right)-\pi \left(x/\mathrm{2}\right)>n-\mathrm{1}$. Let $v_{\mathrm{11}}=\mathrm{1}$, and $v_{\mathrm{22}},\cdots ,v_{nn}$be distinct primes between $x/\mathrm{2}$ and $x$. It is evident that Theorem 2 holds and the proof is complete.

Remark   Erdös-Faber-Lovász conjectured that if the linear hypergraph $H=(X,E)$ has $n$hyperedges and each hyperedge has $n$vertices, then there is a $n$-vertex colour of the hypergraph such that each edge contains vertices of all colours^[8]. Recently, Kang et al^[8] proved that this conjecture holds for every large $n$. Here, we prove that $H=(X,E)$ is prime. Based on our method, one can prove that when $n$is an integer greater than 1, an $n$×$n$grid is a prime hypergraph. In fact, the $n$×$n$grid can be regarded as a linear hypergraph with $\mathrm{2}n$hyperedges ($n$rows and $n$columns) and $n^{\mathrm{2}}$ vertices. On one hand, we have that for $\mathrm{6}<n<\mathrm{17}$, $\pi \left(n^{\mathrm{2}}\right)-\pi \left(n^{\mathrm{2}}/\mathrm{2}\right)\ge n-\mathrm{1}$, and for $n>\mathrm{16}$, $\pi \left(n^{\mathrm{2}}\right)-\pi \left(\mathrm{0.5}{n}^{\mathrm{2}}\right)>\mathrm{0.3}{n}^{\mathrm{2}}/(\mathrm{l}\mathrm{n}{n}^{\mathrm{2}}-\mathrm{l}\mathrm{n}\mathrm{2})>n$.On the other hand, denote those vertices in its principal diagonal by $v_{\mathrm{11}},v_{\mathrm{22}},\cdots ,v_{nn}.$ Let $v_{\mathrm{11}}=\mathrm{1}$ and $v_{\mathrm{22}},\cdots ,v_{nn}$be distinct primes between $n^{\mathrm{2}}/\mathrm{2}$ and $n^{\mathrm{2}}$. Do the cases $\mathrm{1}<n<\mathrm{7}$ separately. This immediately confirms the previous assertion that a $n$×$n$grid is a prime hypergraph.

References