A graph \(G\) is said to be a an interval graph, if for each vertex \(u\) of \(G\), one can assign a set \(A_u\) which is a finite union of intervals on the real line such that \(u\) is adjacent to \(v\) in \(G\) if and only if \(A_u\cap A_v\neq\varnothing\). In this paper, we introduce a class of intersection graphs and show that it is equivalent to the class of interval graphs. We also investigate interval numbers of certain intersection graphs and establish several related results.
In recent years, intersection graph classes have been widely studied beyond classical interval graphs, both from structural and algorithmic perspectives. A prominent direction concerns multiple-interval and \(t\)-interval graphs, where each vertex is represented by a bounded union of intervals on the real line. These generalisations have been studied extensively from an algorithmic perspective, including approximation algorithms and hardness results (see, e.g., [7, 2]), as well as in recent structural developments involving interval representations (see, e.g., [1, 12]). In parallel, geometric intersection graph classes have been extensively studied, particularly through representations by curves, segments, and paths in the plane. Notable developments include intersection representations by grid paths and their generalisations, as well as broader frameworks such as \(H\)-graphs, which unify many classical graph classes (see, e.g., [4, 5, 6].
In this paper, we investigate a class of intersection graphs equivalent to interval graphs and their interval numbers. All the graphs are simple and finite. The vertex set and edge set of a graph \(G\) will be denoted by \(V(G)\) and \(E(G)\), respectively. We write \(u\sim_G v\) if \(uv\) is an edge in \(E(G)\).
Let \(\mathbb R\) be the set of real numbers. An interval of \(\mathbb R\) is denoted by \[ [a,b]=\{x\in\mathbb R\ :\ a\leq x\leq b\}. \]
We allow \(a=b\) and in this scenario \([a,a]=\{a\}\) is just a singleton. A disjoint union of \(m\)-intervals, say \(A\), is of the following form \[\begin{aligned} A=[a_1,b_1]\cup [a_2,b_2]\cup\cdots\cup [a_m,b_m], \end{aligned}\] where \(b_j<a_{j+1}\) for \(1\leq j\leq m-1\). Furthermore, we say \([a_j,b_j]\) is an interval appearing in \(A\). For each integer \(k\geq 1\), let \[\begin{aligned} \mathcal P_k= \{ A\subseteq\mathbb R\ :\ A\ \ \text{is a disjoint union of at most $k$-intervals}\}. \end{aligned}\]
Note that \(\mathcal P_{k'}\subseteq \mathcal P_k\) if \(k'\leq k\). Set \(\mathcal P=\bigcup_{k\geq 1}\mathcal P_k\). Let \(V\) be a finite set. For each \(u\in V\), let \(A_u\in\mathcal P\). We allow \(A_u=A_v\) for \(u\neq v\). The graph \(\mathfrak D\left( \{ A_u\}_{u\in V}\right)\) is defined to be the graph with vertex set \(V\) and for all \(u,v\in V\), \(u\) is adjacent to \(v\) if and only if \(A_u\cap A_v\neq\varnothing\). If \(A_u\in \mathcal P_k\) for all \(u\in V\), then \(\mathfrak D\left( \{ A_u\}_{u\in V}\right)\) is called a \(k\)-interval graph. A graph \(G\) is said to have a \(k\)-interval representation if there exists \(\mathcal A=\{A_u\}_{u\in V(G)}\subseteq \mathcal P_k\) such that \(G= \mathfrak D(\mathcal A)\).
Given a graph \(G\), the interval number \(i(G)\) is defined to be the smallest positive integer \(k\) such that \(G\) has a \(k\)-interval representation, i.e., \[\begin{aligned} i(G)=\min \left\{ k\in\mathbb N\ :\ G= \mathfrak D(\{A_u\}_{u\in V(G)})\ \ \text{for some}\ \ \{A_u\}_{u\in V(G)}\subseteq \mathcal P_k\right\}. \end{aligned}\]
The interval number was introduced by Trotter and Harary [14] in 1979. Later, Scheinerman and West [13] constructed planar graphs with interval number at least 3 and proved the following theorem.
Theorem 1.1. If \(G\) is planar, then \(i(G)\leq 3\).
However, there is a flaw in the proof and this is pointed out by Guégan et al. [9]. An alternative proof of Theorem 1.1 is given by Guégan et al. [10] recently. We refer readers to [3] and [8] for interval numbers of other classes of planar graphs and general graphs.
In this paper, we will consider intersection graph, which we will describe shortly. Let \(\mathbb N\) be the set of positive integers and let \[\begin{aligned} 2^{\mathbb N}_{0}= \{ A\subseteq\mathbb N\ :\ A\ \ \text{is finite}\}. \end{aligned}\]
Let \(V\) be a finite set. For each \(u\in V\), let \(B_u\in 2^{\mathbb N}_{0}\). We allow \(B_u=B_v\) for \(u\neq v\). The graph \(\mathfrak F\left( \{ B_u\}_{u\in V}\right)\) is defined to be the graph with vertex set \(V\) and for all \(u,v\in V\), \(u\) is adjacent to \(v\) if and only if \(B_u\cap B_v\neq\varnothing\). The graph \(\mathfrak F\left( \{ B_u\}_{u\in V}\right)\) is called an intersection graph. The class of all the intersection graphs is denoted by \(\mathcal T_1\). Basically, a graph \(G\) is in \(\mathcal T_1\) if there exists \(\mathcal B=\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\) such that \(G= \mathfrak F(\mathcal B)\).
For each \(B\in 2^{\mathbb N}_{0}\) and \(B\neq \varnothing\), we define \(g(B)=\{X_1,X_2,\dots, X_l\}\) to be the partition of \(B\) such that
\(B=\bigcup_{i=1}^l X_i\),
\(X_i\cap X_j=\varnothing\) for \(i\neq j\),
for each \(i\), the set \(X_i\) consists of consecutive integers, i.e., \(X_i=\{a_i, a_i+1,\dots, a_i+s_i\}\),
for each \(i\) \((1\leq i\leq l-1)\), \(a<b\) for all \(a\in X_i\) and \(b\in X_{i+1}\),
for each \(i\) \((1\leq i\leq l-1)\), \(X_i\cup X_{i+1}\) is not a set consists of consecutive integers.
Conditions (i) and (ii) are definition for partition, whereas conditions (iii), (iv) and (v) are used to show that \(g(B)\) is unique. By conditions (iv) and (v), if \(a_i+s_i\) is the largest integer in \(X_i\) and \(a_{i+1}\) is the smallest integer in \(X_{i+1}\), then \(a_i+s_i+1<a_{i+1}\). Note that \(\vert g(B)\vert=l\) is the number of elements of the partition of \(B\) satisfying conditions (i) to (v). Each \(X_i\) is called a consecutive part of the partition \(g(B)\). If \(X_i=\{a_i, a_i+1,\dots, a_i+s_i\}\), then \(a_i\) is called the initial point of the consecutive part \(X_i\) and \(a_i+s_i\) is called the terminal point of the consecutive part \(X_i\). An element in \(X_i\) is called a middle point if it is not an initial point or a terminal point. For convenience if \(B=\varnothing\), we set \(g(B)=\varnothing\). Note that if \(B=\{1,2,4,5,7,9,10,11,15,16,17,18\}\), then \(g(B)=\{\{1,2\},\{4,5\},\{7\},\{9,10,11\},\{15,16,17,18\}\}\). Furthermore, \(\{1,2\}\) is a consecutive part of \(g(B)\) and 1 is the initial point of \(\{1,2\}\) whereas 2 is the terminal point of \(\{1,2\}\). Note that 7 is the initial point and also the terminal point of the consecutive part \(\{7\}\).
For \(k\geq 1\), let \[\begin{aligned} 2^{\mathbb N}_{0}(k)= \{ A\in 2^{\mathbb N}_{0}\ :\ \vert g(A)\vert\leq k\}. \end{aligned}\]
Let \[\begin{aligned} \mathcal T_1(k)=\left\{ \mathfrak F(\mathcal B)\ :\ \mathcal B=\{B_u\}_{u\in V}\subseteq 2^{\mathbb N}_{0}(k)\ \ \text{for some finite set $V$}\right\}. \end{aligned}\]
Note that \(\mathcal T_1=\bigcup_{k\geq 1} \mathcal T_1 (k)\) and \(\mathcal T_1(k')\subseteq \mathcal T_1(k)\) if \(k'\leq k\).
In Section 2, we showed that interval graphs are equivalent to intersection graph (Theorem 2.8). In Section 3, we introduce the class of 1-intersection graphs, \(\mathcal T_2\) and define the \(\mathcal T_2\)-interval number, \(i_{\mathcal T_2}(G)\). We determine all the graphs with \(i_{\mathcal T_2}(G)=1\) (Theorem 3.10). In Section 4, we showed if \(G\) is planar, then \(i_{\mathcal T_2}(G)\leq 3\) (Theorem 4.8). Finally, in Section 5, we introduce the minimum size number and use it to characterize the triangle free graphs (Theorem 5.5).
Recall that we allow an interval to be of the form \([a,a]=\{a\}\). We shall show that if \(G\) has a \(k\)-interval representation, i.e., \(G= \mathfrak D(\{A_u\}_{u\in V(G)})\) for some \(\{A_u\}_{u\in V(G)}\subseteq \mathcal P_k\), then all the \(A_u\) can be chosen to be singleton free (all intervals appearing in \(A_u\) are not singleton) (Lemma 2.2). In this section, we also will prove Theorem 2.8 which states that a graph has a \(k\)-interval representation if and only if it is in \(\mathcal T_1(k)\).
Lemma 2.1. Let \(Q\) be the union of \(t\) intervals. If \(a\notin Q\), then there exists an \(\epsilon>0\) such that \[\begin{aligned} [a-\epsilon,a+\epsilon]\cap Q=\varnothing. \end{aligned}\]
Proof. Let \(Q=\bigcup_{i=1}^t [c_i,d_i]\). Since \(a\notin [c_i,d_i]\), there exists an \(\epsilon_i>0\) such that \([a-\epsilon_i,a+\epsilon_i]\cap [c_i,d_i]=\varnothing\). Let \(\epsilon=\min_{1\leq i\leq t} \epsilon_i\). Then, \([a-\epsilon,a+\epsilon]\cap Q=\varnothing\). \(\square\)
Let \(\mathcal A=\{A_u\}_{u\in V}\subseteq \mathcal P_k\). Note that for each \(u\in V\), \[\begin{aligned} A_u= [a_{u1}, b_{u1}]\cup [a_{u2}, b_{u2}]\cup\cdots\cup [a_{uk_u}, b_{uk_u}], \end{aligned}\] where \(k_u\leq k\) and \(b_{uj}<a_{u(j+1)}\) for \(1\leq j\leq k_u-1\). Suppose there exists a \(u_0\in V\) with \(c=a_{u_0j_0}=b_{u_0j_0}\). Let \(Q\) be the union of all the intervals \([a_{uj},b_{uj}]\) for which \(c\notin [a_{uj},b_{uj}]\). By Lemma 2.1, we can replace \([a_{u_0j_0},b_{u_0j_0}]=\{c\}\) in \(A_{u_0}\) with \([c-\epsilon,c+\epsilon]\) and \([c-\epsilon,c+\epsilon]\cap Q=\varnothing\). Let \[\begin{aligned} A_{u_0}' =& [a_{u_01}, b_{u_01}]\cup\cdots\cup [a_{u_0(j_0-1)}, b_{u_0(j_0-1)}]\cup [c-\epsilon,c+\epsilon]\cup\\& [a_{u_0(j_0+1)}, b_{u_0(j_0+1)}]\cup\cdots\cup [a_{u_0k_{u_0}}, b_{u_0k_{u_0}}]. \end{aligned}\]
Note that \(\mathfrak D\left(\mathcal A\right)=\mathfrak D\left(\mathcal A'\right)\) where \(\mathcal A'=\{A_u\}_{u\in V\setminus \{u_0\}}\cup \{A_{u_0}'\}\). Therefore, given an \(k\)-interval graph \(\mathfrak D\left( \{ A_u\}_{u\in V}\right)\), by applying Lemma 2.1 repeatedly, we may obtain the same graph \(\mathfrak D\left( \{ A_u'\}_{u\in V}\right)=\mathfrak D\left( \{ A_u\}_{u\in V}\right)\) and each interval in \(A_u'\) is not a singleton for all \(u\in V\). Hence, we have proved the following lemma.
Lemma 2.2. Let \(\mathfrak D\left( \{ A_u\}_{u\in V}\right)\) be a \(k\)-interval graph. There exists \(\{ A_u'\}_{u\in V}\) such that
for all \(u\in V\), if \(A_u\in \mathcal P_k\), then \(A_u'\in \mathcal P_k\),
for all \(u\in V\), all intervals appearing in \(A_u'\) are not singleton,
\(\mathfrak D\left( \{ A_u'\}_{u\in V}\right)=\mathfrak D\left( \{ A_u\}_{u\in V}\right)\).
Now, let \(V\) be a finite set and \(\mathcal B=\{B_u\}_{u\in V}\subseteq 2^{\mathbb N}_{0}(k)\). Then, \(\vert g(B_u)\vert \leq k\) for all \(u\in V\). Let \(g(B_u)=\{X_{u1},X_{u2},\dots, X_{uk_u}\}\). Then, \(k_u\leq k\). For each \(i\), let \(X_{ui}=\{a_{ui}, a_{ui}+1,\dots, a_{ui}+s_{ui}\}\). Now, for each \(u\in V\), set \[\begin{aligned} A_u=[a_{u1},a_{u1}+s_{u1}]\cup [a_{u2},a_{u2}+s_{u2}]\cup \cdots\cup [a_{uk_u},a_{uk_u}+s_{uk_u}]. \end{aligned}\]
Note that \(A_u\) is a disjoint union of \(k_u\) intervals and \(A_u\in \mathcal P_k\). Furthermore, \(A_u\cap A_v\neq \varnothing\) if and only if \(B_u\cap B_v\neq \varnothing\). This implies that \(\mathfrak D(\mathcal A)= \mathfrak F(\mathcal B)\) where \(\mathcal A=\{A_u\}_{u\in V}\). The following lemma then follows from Lemma 2.2.
Lemma 2.3. If \(G\in \mathcal T_1(k)\), then there exists \(\mathcal A=\{A_u\}_{u\in V(G)}\subseteq \mathcal P_k\) such that \(G= \mathfrak D(\mathcal A)\). Furthermore, all intervals appearing in each \(A_u\) are not singleton.
The next two lemmas explain what will happen to \(g(B)\) if an element is added or removed from \(B\).
Lemma 2.4. Let \(B\in 2^{\mathbb N}_{0}\) be non-empty and \(c\in \mathbb N\setminus B\). Then the followings hold:
if \(c+1\) is not the initial point of a consecutive part of \(g(B)\) and \(c-1\) is not the terminal point of a consecutive part of \(g(B)\), then \(\vert g(B\cup \{c\})\vert= \vert g(B)\vert+1\),
if either \(c+1\) is the initial point of a consecutive part of \(g(B)\) or \(c-1\) is the terminal point of a consecutive part of \(g(B)\) but not both, then \(\vert g(B\cup \{c\})\vert= \vert g(B)\vert\),
if \(c+1\) is the initial point of a consecutive part of \(g(B)\) and \(c-1\) is the terminal point of a consecutive part of \(g(B)\), then \(\vert g(B\cup \{c\})\vert= \vert g(B)\vert-1\).
Proof. (a) Note that \(\{c\}\) is a consecutive part of \(g(B\cup \{c\})\) and each consecutive part of \(g(B)\) is also a consecutive part of \(g(B\cup \{c\})\). Hence, \(\vert g(B\cup \{c\})\vert= \vert g(B)\vert+1\).
(b) Suppose \(c+1\) is the initial point of a consecutive part of \(g(B)\) and \(c-1\) is not the terminal point of a consecutive part of \(g(B)\). This implies that \(c-1\notin B\). Note that if \(c+1\) is the initial point of a consecutive part of \(g(B)\), say \(X\), then \(X\cup \{c\}\) is also a consecutive part of \(g(B\cup \{c\})\) for \(c-1\notin B\). Each consecutive part of \(g(B)\) that do not contain \(c+1\) is also a consecutive part of \(g(B\cup \{c\})\). Hence, \(\vert g(B\cup \{c\})\vert= \vert g(B)\vert\). Similarly, if \(c-1\) is the terminal point of a consecutive part of \(g(B)\) and \(c+1\) is not the initial point of a consecutive part of \(g(B)\), then \(\vert g(B\cup \{c\})\vert= \vert g(B)\vert\).
(c) If \(c+1\) is the initial point of a consecutive part of \(g(B)\), say \(X_1\), and \(c-1\) is the terminal point of a consecutive part of \(g(B)\), say \(X_2\), then \(X_1\cup X_2\cup \{c\}\) is a consecutive part of \(g(B\cup \{c\})\). Each consecutive part of \(g(B)\) that do not contain \(c+1\) or \(c-1\) is also a consecutive part of \(g(B\cup \{c\})\). Hence, \(\vert g(B\cup \{c\})\vert= \vert g(B)\vert-1\). \(\square\)
Lemma 2.5. Let \(B\in 2^{\mathbb N}_{0}\) be non-empty and \(c\in B\). Then the following hold:
if \(c\) is the initial point or the terminal point of a consecutive part of \(g(B)\), then \(\vert g(B\setminus \{c\})\vert= \vert g(B)\vert\),
if \(c\) is a middle point of a consecutive part of \(g(B)\), then \(\vert g(B\setminus \{c\})\vert= \vert g(B)\vert+1\).
Proof. (a) Suppose \(c\) is the initial point of a consecutive part of \(g(B)\), say \(X\). Then \(X=\{c,c+1,\dots, c+m\}\) for some non-negative integer \(m\). Note that \(X\setminus \{c\}\) is a consecutive part of \(g(B\setminus\{c\})\). Each consecutive part of \(g(B)\) that do not contain \(c\) is also a consecutive part of \(g(B\setminus \{c\})\). Hence, \(\vert g(B\setminus \{c\})\vert= \vert g(B)\vert\). Similarly, the same conclusion holds if \(c\) is the terminal point of a consecutive part of \(g(B)\).
(b) Let \(X\) be the consecutive part of \(g(B)\) that contains \(c\). Since \(c\) is a middle point of \(X\), we have \(X=\{c-m_1,\dots, c-1,c,c+1,\dots, c+m_2\}\) for some positive integers \(m_1,m_2\). Note that \(\{c-m_1,\dots, c-1\}\) and \(\{c+1,\dots, c+m_2\}\) are consecutive parts of \(g(B\setminus \{c\})\). Each consecutive part of \(g(B)\) that do not contain \(c\) is also a consecutive part of \(g(B\setminus \{c\})\). Hence, \(\vert g(B\setminus \{c\})\vert= \vert g(B)\vert+1\). \(\square\)
For each \(B\in 2^{\mathbb N}_{0}\), \(B\neq \varnothing\) and any integer \(p\), we set \[\begin{aligned} B+p=\{b+p\ :\ b\in B\}. \end{aligned}\]
Lemma 2.6. Let \(B_1,B_2\in 2^{\mathbb N}_{0}\) be non-empty and \(p\) be an integer. Then \(B_1\cap B_2=\varnothing\) if and only if \((B_1+p)\cap (B_2+p)=\varnothing\). Furthermore, if \(B_1\cap B_2\neq \varnothing\), then \((B_1+p)\cap (B_2+p)=(B_1\cap B_2)+p\).
Proof. Suppose \(B_1\cap B_2\neq \varnothing\). Then, \(((B_1\cap B_2)+p)\subseteq (B_1+p)\cap (B_2+p)\). Let \(y\in (B_1+p)\cap (B_2+p)\). Then, \(y=b_1+p=b_2+b\) for some \(b_1\in B_1\) and \(b_2\in B_2\). This implies that \(b_1=b_2\in B_1\cap B_2\). Hence, \(y\in (B_1\cap B_2)+p\) and \((B_1+p)\cap (B_2+p)=(B_1\cap B_2)+p\).
If \((B_1+p)\cap (B_2+p)\neq \varnothing\), then by the previous paragraph, \(B_1\cap B_2=((B_1+p)\cap (B_2+p))-p\neq \varnothing\). This completes the proof of the lemma. \(\square\)
Lemma 2.7. Let \([a,b]\) be an interval in \(\mathbb R\) and \(c\in\mathbb R\) such that \(a<c\leq b\). If \([z_1,z_2]\) is an interval in \(\mathbb R\) such that \([z_1,z_2]\cap [a,b]\neq\varnothing\) and \(z_1\geq c\), then \([z_1,z_2]\cap [c,b]\neq\varnothing\).
Proof. Since \([z_1,z_2]\cap [a,b]\neq\varnothing\), there is a \(y\in [z_1,z_2]\cap [a,b]\). This implies that \(y\geq z_1\geq c\). Since \(y\leq b\), we have \(y\in [c,b]\). Hence, \(y\in [z_1,z_2]\cap [c,b]\) and \([z_1,z_2]\cap [c,b]\neq\varnothing\). \(\square\)
Given a graph \(G\) and a vertex \(u\in V(G)\), the graph obtained from \(G\) by removing \(u\) and all edges incident to it is denoted by \(G-u\). If \(S\subseteq V(G)\), then \(G-S\) is the graph obtained by removing all vertices in \(S\) and all edges incident to them from \(G\). We write \(G[S]\) to denote the induced subgraph of \(G\) with vertex set \(S\).
For each \(A\subseteq \mathcal P\) and \[\begin{aligned} A= [x_{1}, y_{1}]\cup [x_{2}, y_{2}]\cup\cdots\cup [x_{m}, y_{m}], \end{aligned}\] where \(y_{i}<x_{i+1}\) for \(1\leq i\leq m-1\), we set \(\min A=x_1\).
Theorem 2.8. A graph \(G\) has a \(k\)-interval representation if and only if \(G\in \mathcal T_1(k)\).
Proof. By Lemma 2.3, it is sufficient to show that if \(G= \mathfrak D(\mathcal A)\) for some \(\mathcal A=\{A_u\}_{u\in V(G)}\subseteq \mathcal P_k\), then \(G\in \mathcal T_1(k)\). Let us first introduce some notations. For each \(u\in V(G)\), let \(t(A_u)\) be the number of disjoint intervals in \(A_u\). Since \(A_u\in \mathcal P_k\), \(t(A_u)\leq k\) for all \(u\in V(G)\). We shall prove the following statement.
Statement: Let \(G= \mathfrak D(\mathcal A)\) for some \(\mathcal A=\{A_u\}_{u\in V(G)}\subseteq \mathcal P_k\). If \(c=\min \{\min A_u\ : \ u\in V(G)\}\), then there exists \(\mathcal B=\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}(k)\) such that \(G=\mathfrak F(\mathcal B)\in \mathcal T_1(k)\), \(\vert g(B_u)\vert\leq t(A_u)\) for all \(u\in V(G)\) and \(1\in B_v\) for all \(v\in V(G)\) satisfying \(\min A_v=c\).
We shall prove the statement by induction on \(T=\sum\limits_{u\in V(G)} t(A_u)\). Note that \(T\geq \vert V(G)\vert\) and equality holds if and only if \(t(A_u)=1\) for all \(u\).
If \(T=1\), then \(G\) consists of a single vertex, say \(u_0\). Set \(B_{u_0}=\{1\}\). Then, the statement holds. So, we may assume that \(T\geq 2\). Assume that the statement holds for any graph \(G'=\mathfrak D(\{A_u'\}_{u\in V(G')})\) with \(\{A_u'\}_{u\in V(G')}\subseteq \mathcal P_k\) satisfying \(\sum\limits_{u\in V(G')} t(A_u')<T\).
For each \(u\in V(G)\), let \[\begin{aligned} A_u= [x_{u1}, y_{u1}]\cup [x_{u2}, y_{u2}]\cup\cdots\cup [x_{uk_u}, y_{uk_u}], \end{aligned}\] where \(y_{ui}<x_{u(i+1)}\) for \(1\leq i\leq k_u-1\). Then, \(t(A_u)=k_u\leq k\) and \(\min A_u=x_{u1}\).
Let \[\begin{aligned} W(\{A_u\}_{u\in V(G)})=\bigcup_{u\in V(G)} \{x_{u1},y_{u1},x_{u2},y_{u2},\dots,x_{uk_u},y_{uk_u}\}. \end{aligned}\]
If \(\vert W(\{A_u\}_{u\in V(G)})\vert=1\), then \(k_u=1\) and \(x_{u1}=y_{u1}=c\) for all \(u\in V(G)\). This implies that \(G= \mathfrak D(\mathcal A)\) is the complete graph \(K_n\) where \(n=\vert V(G)\vert\). Let \(B_u=\{1\}\) for all \(u\) and \(\mathcal B=\{B_u\}_{u\in V(G)}\). Then, \(\mathcal B\subseteq 2^{\mathbb N}_{0}(1)\) and \(\mathfrak F(\mathcal B)\) is the complete graph \(K_n\). Hence, \(G= \mathfrak F(\mathcal B)\in \mathcal T_1(1)\), \(\vert g(B_u)\vert=t(A_u)=1\) for all \(u\in V(G)\) and \(1\in B_v\) for all \(v\) satisfying \(x_{v}=c\).
Suppose \(w_0=\vert W(\{A_u\}_{u\in V(G)})\vert>1\). We shall assume that the statement holds for any graph \(G'=\mathfrak D(\{A_u'\}_{u\in V(G')})\) with \(\{A_u'\}_{u\in V(G')}\subseteq \mathcal P_k\) satisfying \(\sum\limits_{u\in V(G')} t(A_u')=T\) and \(1\leq \vert W(\{A_u'\}_{u\in V(G')})\vert<w_0\). Note that \(c=\min\{ x_{u1}\ :\ {u\in V(G)}\}\). Let \(u_1,u_2,\dots, u_r\) be the only vertices in \(V(G)\) with \(x_{u_j1}=c\). By relabelling if necessary we may assume that \(y_{u_11}\leq y_{u_21}\leq \cdots\leq y_{u_r1}\).
Case 1. Suppose \(x_{u_j1}=y_{u_j1}\) for all \(1\leq j\leq p\) where \(1\leq p\leq r\) and \(c=x_{u_{j}1}<y_{u_{j}1}\) for \(p+1\leq j\leq r\).
Suppose \(r=p\). We may assume that \(t(A_{u_j})=k_{u_j}=1\) for \(1\leq j\leq q\) and \(t(A_{u_j})=k_{u_j}\geq 2\) for \(q+1\leq j\leq p\). For \(q+1\leq j\leq p\), let \(A_{u_j}'=A_{u_j}\setminus \{c\}\). Then, \[\begin{aligned} A_{u_j}'= [x_{{u_j}2}, y_{{u_j}2}]\cup [x_{{u_j}3}, y_{{u_j}3}]\cup\cdots\cup [x_{{u_j}k_{u_j}}, y_{{u_j}k_{u_j}}], \end{aligned}\] and \(t(A_{u_j}')=k_{u_j}-1\). For other \(u\in V(G)\setminus\{u_1,u_2,\dots, u_p\}\), we set \(A_u'=A_u\). Now, let \(G'=\mathfrak D(\{A_u'\}_{u\in V(G')})\). Note that \(G'\) is a subgraph of \(G\), \(V(G')=V(G)\setminus \{u_1,u_2,\dots ,u_q\}\) and \(\sum\limits_{u\in V(G')} t(A_u')=T-p<T\). By induction, there exists \(\mathcal B''=\{B_u''\}_{u\in V(G')}\subseteq 2^{\mathbb N}_{0}(k)\) such that \(G'=\mathfrak F(\mathcal B'')\in \mathcal T_1(k)\), \(\vert g(B_u'')\vert\leq t(A_u')\) for all \(u\in V(G')\) and \(1\in B_v''\) for all \(v\) satisfying \(\min A_v'=c'\) where \(c'=\min \{\min A_u'\ :\ {u\in V(G')} \}\). Now, we need to ‘add back’ vertices \(u_1,u_2,\dots ,u_q\) to \(G'\) to become \(G\). Note that for \(q+1\leq j\leq p\), \(\vert g(B_{u_j}'')\vert\leq k_{u_j}-1\). Set \(B_u'=B_u''+1\) for all \(u\in V(G')\). Clearly, \(\vert g(B_u')\vert=\vert g(B_u'')\vert\). By Lemma 2.6, \(G'=\mathfrak F(\{B_u'\}_{u\in V(G')})\). Now, we set \(B_{u_j}=\{1\}\) for \(1\leq j\leq q\), \(B_{u_j}=\{1\}\cup B_{u_j}'\) for \(q+1\leq j\leq p\) and \(B_u=B_u'\) for other \(u\) in \(V(G)\setminus \{u_1,u_2,\dots ,u_p\}\). Then, \(\vert g(B_{u_j})\vert=t(A_{u_j})=1\) for \(1\leq j\leq q\). By Lemma 2.4, \(\vert g(B_{u_j})\vert\leq \vert g(B_{u_j}')\vert+1\leq (k_{u_j}-1)+1=t(A_{u_j})\) for \(q+1\leq j\leq p\). For other \(u\in V(G)\setminus \{u_1,u_2,\dots ,u_p\}\), \(\vert g(B_u)\vert =\vert g(B_u')\vert\leq t(A_u')=t(A_u)\). Now, \(1\in B_{u_j}\) for all \(1\leq j\leq p\), \(\mathcal B=\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}(k)\) and \(G=\mathfrak F(\mathcal B)\in \mathcal T_1(k)\). Hence, the statement holds for the graph \(G\).
Suppose \(r>p\). By Lemma 2.1, there is an \(\epsilon>0\) such that \([c-\epsilon,c+\epsilon]\cap A_u=\varnothing\) for all \(u\in V(G)\setminus \{u_1,u_2,\dots, u_r\}\). The \(\epsilon\) can be chosen so that \(c+\epsilon< y_{u_j1}\) for \(p+1\leq j\leq r\). Now, for \(p+1\leq j\leq r\), let \[A_{u_j}'=[c+\epsilon, y_{u_j1}]\cup [x_{{u_j}2}, y_{{u_j}2}]\cup [x_{{u_j}3}, y_{{u_j}3}]\cup\cdots\cup [x_{{u_j}k_{u_j}}, y_{{u_j}k_{u_j}}].\]
By relabelling if necessary, we may assume that \(t(A_{u_j})=k_{u_j}=1\) for \(1\leq j\leq q\) and \(t(A_{u_j})=k_{u_j}\geq 2\) for \(q+1\leq j\leq p\). For \(q+1\leq j\leq p\), let \(A_{u_j}'=A_{u_j}\setminus \{c\}\). Then, \[\begin{aligned} A_{u_j}'= [x_{{u_j}2}, y_{{u_j}2}]\cup [x_{{u_j}3}, y_{{u_j}3}]\cup\cdots\cup [x_{{u_j}k_{u_j}}, y_{{u_j}k_{u_j}}], \end{aligned}\] and \(t(A_{u_j}')=k_{u_j}-1\). Finally, for other \(u\in V(G)\setminus \{u_1,u_2,\dots, u_r\}\), let \(A_u'=A_u\). Note that \(t(A_{u}')=t(A_u)\) for all \(u\in V(G)\setminus \{u_1,u_2,\dots, u_p\}\). Now, let \(G'=\mathfrak D(\{A_u'\}_{u\in V(G')})\). Note that \(G'\) is a subgraph of \(G\), \(V(G')=V(G)\setminus \{u_1,u_2,\dots ,u_q\}\) and \(\sum\limits_{u\in V(G')} t(A_u')=T-p<T\). By induction, there exists \(\mathcal B''=\{B_u''\}_{u\in V(G')}\subseteq 2^{\mathbb N}_{0}(k)\) such that \(G'=\mathfrak F(\mathcal B'')\in \mathcal T_1(k)\), \(\vert g(B_u'')\vert\leq t(A_u')\) for all \(u\in V(G')\) and \(1\in B_v''\) for all \(v\) satisfying \(\min A_v'=c'\) where \(c'=\min \{\min A_u'\ :\ {u\in V(G')} \}\). Note that \(c'=c+\epsilon\). Therefore, \(1\in B_{u_j}''\) for \(p+1\leq j\leq r\). Now, we shall ‘add back’ vertices \(u_1,u_2,\dots ,u_q\) to \(G'\) to become \(G\). Note that for \(q+1\leq j\leq p\), \(\vert g(B_{u_j}'')\vert\leq k_{u_j}-1\). Set \(B_u'=B_u''+1\) for all \(u\in V(G')\). Clearly, \(\vert g(B_u')\vert=\vert g(B_u'')\vert\). By Lemma 2.6, \(G'=\mathfrak F(\{B_u'\}_{u\in V(G')})\). Now, we set \(B_{u_j}=\{1\}\) for \(1\leq j\leq q\), \(B_{u_j}=\{1\}\cup B_{u_j}'\) for \(q+1\leq j\leq r\) and \(B_u=B_u'\) for other \(u\) in \(V(G)\setminus \{u_1,u_2,\dots ,u_r\}\). Then, \(\vert g(B_{u_j})\vert=t(A_{u_j})=1\) for \(1\leq j\leq q\). Since \(1\in B_{u_j}''\) for \(p+1\leq j\leq r\) and \(B_{u_j}'=B_{u_j}''+1\), we have \(2\in B_{u_j}'\) and \(1\notin B_{u_j}'\). By Lemma 2.4, \(\vert g(B_{u_j})\vert= \vert g(B_{u_j}')\vert\leq k_{u_j}=t(A_{u_j})\) for \(p+1\leq j\leq r\). Again, by Lemma 2.4, \(\vert g(B_{u_j})\vert= \vert g(B_{u_j}')\vert\leq (k_{u_j}-1)+1=t(A_{u_j})\) for \(q+1\leq j\leq p\). For other \(u\in V(G)\setminus \{u_1,u_2,\dots ,u_r\}\), \(\vert g(B_u)\vert =\vert g(B_u')\vert\leq t(A_u')= t(A_u)\). Now, \(1\in B_{u_j}\) for all \(1\leq j\leq r\), \(\mathcal B=\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}(k)\) and \(G=\mathfrak F(\mathcal B)\in \mathcal T_1(k)\). Hence, the statement holds.
Case 2. Suppose \(c=x_{u_{j}1}<y_{u_{j}1}\) for \(1\leq j\leq r\).
Assume that there is a vertex \(u_0\) such that \(c<x_{u_0}\leq y_{u_11}\) and \(x_{u_0}\leq x_u\) for other \(u\in V(G)\setminus \{u_1,u_2,\dots, u_r\}\). For \(1\leq j\leq r\), let \[A_{u_j}'=[x_{u_0},y_{u_j1}]\cup [x_{{u_j}2}, y_{{u_j}2}]\cup [x_{{u_j}3}, y_{{u_j}3}]\cup\cdots\cup [x_{{u_j}k_{u_j}}, y_{{u_j}k_{u_j}}],\] and for other \(u\in V(G)\setminus \{u_1,u_2,\dots, u_r\}\) let \(A_u'=A_u\). By Lemma 2.7, \(G= \mathfrak D(\{A_u'\}_{u\in V(G)})\). Since \(t(A_u')=t(A_u)\) for all \(u\in V(G)\), \(\sum\limits_{u\in V(G)} t(A_u')=\sum\limits_{u\in V(G)} t(A_u)=T\). On the other hand, \(\vert W(\{A_u'\}_{u\in V(G)})\vert=w_0-1<w_0\). By induction, there exists \(\mathcal B=\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}(k)\) such that \(G=\mathfrak F(\mathcal B)\in \mathcal T_1(k)\), \(\vert g(B_u)\vert\leq t(A_u)\) for all \(u\in V(G)\) and \(1\in B_v\) for all \(v\) satisfying \(\min A_v'=c'\) where \(c'=\min \{\min A_u'\ :\ {u\in V(G)}\}\). Note that \(c'=x_{u_0}\). So, in particular, \(1\in B_{u_j}\) for all \(1\leq j\leq r\). Hence, the statement holds.
Suppose for all \(u\in V(G)\setminus \{u_1,u_2,\dots, u_r\}\), \(x_u\geq y_{u_{1}1}\). For \(1\leq j\leq r\), let \[A_{u_j}'=[y_{u_11},y_{u_j1}]\cup [x_{{u_j}2}, y_{{u_j}2}]\cup [x_{{u_j}3}, y_{{u_j}3}]\cup\cdots\cup [x_{{u_j}k_{u_j}}, y_{{u_j}k_{u_j}}],\] and for other \(u\in V(G)\setminus \{u_1,u_2,\dots, u_r\}\) let \(A_u'=A_u\). By Lemma 2.7, \(G= \mathfrak D(\{A_u'\}_{u\in V(G)})\). Since \(t(A_u')=t(A_u)\) for all \(u\in V(G)\), \(\sum\limits_{u\in V(G)} t(A_u')=\sum\limits_{u\in V(G)} t(A_u)=T\). On the other hand, \(\vert W(\{A_u'\}_{u\in V(G)})\vert=w_0-1<w_0\). By induction, there exists \(\mathcal B=\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}(k)\) such that \(G=\mathfrak F(\mathcal B)\in \mathcal T_1(k)\), \(\vert g(B_u)\vert\leq t(A_u)\) for all \(u\in V(G)\) and \(1\in B_v\) for all \(v\) satisfying \(\min A_v'=c'\) where \(c'=\min \{\min A_u'\ :\ {u\in V(G)}\}\). Note that \(c'=y_{u_11}\). So, in particular, \(1\in B_{u_j}\) for all \(1\leq j\leq r\). Hence, the statement holds.
This completes the proof of the theorem. \(\square\)
The \(\mathcal T_1\)-interval number \(i_{\mathcal T_1}(G)\) is defined as \[\begin{aligned} i_{\mathcal T_1}(G)=\min \left\{ k\in\mathbb N\ :\ G\in \mathcal T_1 (k)\right\}. \end{aligned}\]
The following corollary is an immediate consequence of Theorem 2.8.
Corollary 2.9. \(i(G)=i_{\mathcal T_1}(G)\).
Recall that the class of all the intersection graphs is denoted by \(\mathcal T_1\). In this section, we will introduce the class of 1-intersection graphs, \(\mathcal T_2\). Let \(V\) be a finite set. Recall that a graph \(G\in \mathcal T_1\) if \(G=\mathfrak F\left( \{ B_u\}_{u\in V}\right)\) for some \(\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\). Here, \(u\sim_G v\) if and only if \(B_u\cap B_v\neq\varnothing\). There is no restriction on the number of elements in \(B_u\cap B_v\). For the class \(\mathcal T_2\), we require that \(\vert B_u\cap B_v\vert\leq 1\). Formally, \[\begin{aligned} \mathcal T_2&=\left\{ \mathfrak F(\mathcal B)\ :\ \mathcal B=\{B_u\}_{u\in V}\subseteq 2^{\mathbb N}_{0}\ \ \text{for some finite set $V$ and}\right.\\ &\hskip 2cm\left. \text{ $\vert B_u\cap B_v\vert\leq 1$ for all $u,v\in V$ with $u\neq v$}\vphantom{2^{\mathbb N}_{0}}\right\}. \end{aligned}\]
For each positive integer \(k\geq 1\), let \[\begin{aligned} \mathcal T_2 (k)&=\left\{ \mathfrak F(\mathcal B)\ :\ \mathcal B=\{B_u\}_{u\in V}\subseteq 2^{\mathbb N}_{0}(k)\ \ \text{for some finite set $V$ and}\right.\\ &\hskip 2cm\left. \text{ $\vert B_u\cap B_v\vert\leq 1$ for all $u,v\in V$ with $u\neq v$}\vphantom{2^{\mathbb N}_{0}}\right\}. \end{aligned}\]
Note that \(\mathcal T_2=\bigcup_{k\geq 1} \mathcal T_2 (k)\) and \(\mathcal T_2(k')\subseteq \mathcal T_2(k)\) if \(k'\leq k\). The following lemma follows from definitions of \(\mathcal T_1(k)\) and \(\mathcal T_2(k)\).
Lemma 3.1. For \(k\geq 1\), \(\mathcal T_2(k)\subseteq \mathcal T_1(k)\).
Lemma 3.2. \(G\in \mathcal T_2\) for any graph \(G\).
Proof. For each \(uv\) in \(E(G)\), we assign a positive integer \(c_{uv}\) to it. The assignment of integers can be done so that \(c_{uv}\neq c_{u'v'}\) for distinct edges \(uv\) and \(u'v'\). Note that \(c_{uv}=c_{vu}\) for all \(u\sim_G v\). Let \(B_u=\{c_{uv}\ :\ v\in N_G(u)\}\) where \(N_G(u)\) is the neighbourhood of \(u\). Since all the \(c_{uv}\)’s are distinct, we have \(B_{u'}\cap B_{v'}=\{c_{u'v'}\}\) for all \(u'\sim_G v'\) and \(B_{u'}\cap B_{v'}=\varnothing\) for all \(u'\not\sim_G v'\). Thus, \(G=\mathcal F(\{B_u\}_{u\in V(G)})\). Furthermore, \(\vert B_u\cap B_v\vert\leq 1\) for all \(u,v\in V(G)\) implies that \(G\in\mathcal T_2\). \(\square\)
The following corollary follows from Lemmas 3.1 and 3.2.
Corollary 3.3. \(\mathcal T_1=\mathcal T_2\).
The \(\mathcal T_2\)-interval number \(i_{\mathcal T_2}(G)\) is defined as \[\begin{aligned} i_{\mathcal T_2}(G)=\min \left\{ k\in\mathbb N\ :\ G\in \mathcal T_2 (k)\right\}. \end{aligned}\]
The following lemma follows from Lemma 3.1.
Lemma 3.4. \(i_{\mathcal T_1}(G)\leq i_{\mathcal T_2}(G)\).
Note that in general, \(i_{\mathcal T_2}(G)\neq i_{\mathcal T_1}(G)\). See the following example.
Example 3.5. Consider the graph \(G\) with the vertex set \(V=\{u,v,w,x\}\), and edges given by \(uv\), \(ux\), \(vx\), \(vw\), \(wx\). Let \(B_u=\{1\}\), \(B_v=\{1,2\}=B_x\) and \(B_w=\{2\}\). Then, \(\mathcal B=\{B_z\}_{z\in V}\subseteq 2^{\mathbb N}_{0}(1)\) and \(G=\mathfrak F(\mathcal B)\in \mathcal T_1(1)\) (see Figure 1). Since each \(B_z\), \(z \in \{u, v, x, w\}\) is a consecutive part, we have \(|g(B_z)| = 1\). Thus \(i_{\mathcal T_1}(G)=1\).
The graph \(G\) can also be realized as a graph in \({\mathcal T_2}\). Let \(C_u=\{1\}\), \(C_v=\{1,2\}\), \(C_w=\{2,3\}\) and \(C_x=\{1,3\}\). Then, \(\vert C_{z_1}\cap C_{z_2}\vert\leq 1\) for all \(z_1,z_2\in V\) with \(z_1\neq z_2\). Furthermore, \(g(C_u)=\{C_u\}\), \(g(C_v)=\{C_v\}\), \(g(C_w)=\{C_w\}\) and \(g(C_x)=\{\{1\},\{3\}\}\). Since \(\vert g(C_x)\vert=2\) and \(\vert g(C_z)\vert=1\) for all \(z\in V\setminus \{x\}\), we have \(\mathcal C=\{C_z\}_{z\in V}\subseteq 2^{\mathbb N}_{0}(2)\) and \(G=\mathfrak F(\mathcal C)\in \mathcal T_2(2)\) (see Figure 1). Thus, \(i_{\mathcal T_2}(G)\leq 2\). We will show that \(i_{\mathcal T_2}(G)=2\).
Suppose \(i_{\mathcal T_2}(G)=1\). Then, there exists \(\{U_z\}_{z\in V}\subseteq 2^{\mathbb N}_{0}(1)\) satisfying \(\vert U_{z_1}\cap U_{z_2}\vert\leq 1\) for all \(z_1,z_2\in V\) with \(z_1\neq z_2\) such that \(G=\mathfrak F(\{U_z\}_{z\in V})\). Note that \(\vert U_{z_1}\cap U_{z_2}\vert=1\) for all \(z_1\sim_G z_2\).
Case 1. Suppose \(U_u\cap U_v=\{a\}=U_{u}\cap U_x\). This implies that \(U_v\cap U_x=\{a\}\). Let \(U_v\cap U_w=\{b\}\) and \(U_w\cap U_x=\{c\}\). We may assume that \(c\geq b\). Since \(u\) is not adjacent to \(w\) in \(G\), we must have \(b,c\neq a\). If \(c=b\), then \(c\in U_v\cap U_x=\{a\}\) and so \(c=a\), a contradiction. Suppose \(c>b\). Assume that \(b>a\). Since \(g(U_x)\) has only one consecutive part (i.e. \(\vert g(U_x)\vert=1\)), \(a,c\in U_x\) and \(c>b>a\), we must have \(b\in U_x\). This implies that \(b\in U_x\cap U_v=\{a\}\) and \(b=a\), a contradiction. Assume that \(b<a\). Suppose \(b<c<a\). Since \(g(U_v)\) has only one consecutive part and \(a,b\in U_v\), we must have \(c\in U_v\). This implies that \(c\in U_v\cap U_x=\{a\}\) and so \(c=a\), a contradiction. Suppose \(b<a<c\). Since \(g(U_w)\) has only one consecutive part and \(b,c\in U_w\), we must have \(a\in U_w\). This implies that \(u\) is adjacent to \(w\) in \(G\), a contradiction.
Case 2. Suppose \(U_u\cap U_v=\{a\}\), \(U_{u}\cap U_x=\{b\}\), \(U_{v}\cap U_x=\{c\}\), \(U_{x}\cap U_w=\{d\}\) and \(U_{v}\cap U_w=\{e\}\). We shall assume that \(a,b,c,d,e\) are distinct integers, otherwise, it will go back to Case 1. Since \(g(U_x)\) has only one consecutive part, \(U_x=\{p,p+1,\dots, p+q\}\). Note that \(b,c,d\in U_x\) and \(a,e\notin U_x\). We may assume that \(e>a\). Now, \(a,e,c\in U_v\), \(b,d\notin U_v\) and \(g(U_v)\) has only one consecutive part imply that \(a>p+q\) or \(e<p\). Suppose \(a>p+q\). Since \(c\leq p+q\) and \(U_{v}\cap U_x=\{c\}\), \(c=p+q\). Now, \(b\notin U_v\) implies that \(b<c\). We consider \(U_u\). Note that \(a,b\in U_u\) and \(g(U_u)\) has only one consecutive part imply that \(c\in U_u\). Thus, \(c\in U_u\cap U_v=\{a\}\) and then \(c=a\), a contradiction. Suppose \(e<p\). Since \(c\geq p\) and \(U_{v}\cap U_x=\{c\}\), \(c=p\). Now, \(d\notin U_v\) implies that \(d>c\). We consider \(U_w\). Note that \(d,e\in U_w\) and \(g(U_w)\) has only one consecutive part imply that \(c\in U_w\). Thus, \(c\in U_w\cap U_v=\{e\}\) and so \(c=e\), a contradiction.
Hence, we conclude that \(i_{\mathcal T_2}(G)=2\) and \(i_{\mathcal T_1}(G)<i_{\mathcal T_2}(G)\).
Now, we shall characterize graph \(G\) with \(i_{\mathcal T_2}(G)=1\). Given any finite set \(V\) and \(\{B_u\}_{u\in V}\subseteq 2^{\mathbb N}_{0}\), let \[\begin{aligned} L(\{B_u\}_{u\in V})=\bigcup_{u\in V} B_u. \end{aligned}\]
Lemma 3.6. Let \(G=\mathfrak F(\{B_u\}_{u\in V(G)})\) for some \(\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\). Then the following statements hold:
Let \(x\) be the smallest positive integer in \(L(\{B_u\}_{u\in V(G)})\), \(p\leq x\) be a positive integer and \(f:\mathbb N\rightarrow\mathbb N\) be defined by \(f(a)=a-p+1\) for all \(a\in \mathbb N\). If \(C_u=f(B_u)=\{ f(a)\ :\ a\in B_u\}\) for all \(u\in V(G)\), then \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\) and \(\vert g(C_u)\vert=\vert g(B_u)\vert\) and \(\vert C_u\cap C_v\vert=\vert B_u\cap B_v\vert\) for all \(u,v\in V(G)\) with \(u\neq v\). In particular, there exists \(\{C_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\) with \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\) and \(1\in L(\{C_u\}_{u\in V(G)})\).
Suppose \(c,d\in L(\{B_u\}_{u\in V(G)})\) with \(c+1<d\) and \(c+1,c+2,\dots, d-1\notin L(\{B_u\}_{u\in V(G)})\). Let \(f:\mathbb N\rightarrow\mathbb N\) be defined by \[\begin{aligned} f(a)=\begin{cases} a, & \text{for $1\leq a\leq d-1$};\\ a-d+c+1,\qquad\vphantom{i} & \text{for $a\geq d$}. \end{cases} \end{aligned}\]
If \(C_u=f(B_u)=\{ f(a)\ :\ a\in B_u\}\) for all \(u\in V(G)\), then \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\) and \(c,c+1\in L(\{C_u\}_{u\in V(G)})\). Furthermore, for all \(u,v\in V(G)\) with \(u\neq v\), \(\vert g(C_u)\vert= \vert g(B_u)\vert\) if \(\{c,d\}\not\subseteq B_u\) and \(\vert g(C_u)\vert= \vert g(B_u)\vert-1\) if \(\{c,d\}\subseteq B_u\).
Suppose \(c\in B_{u_0}\) for exactly one \(u_0\in V(G)\). Let \(C_{u_0}=B_{u_0}\setminus \{c\}\) and \(C_u=B_u\) for all \(u\in V(G)\setminus \{c\}\). Then \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\).
Proof. (a) It follows from Lemma 2.6 by noting that \(C_u=B_u-p+1\). Furthermore, if \(g(B_u)=\{X_1,X_2,\dots, X_{m}\}\), then \(g(C_u)=\{X_1-p+1,X_2-p+1,\dots, X_{m}-p+1\}\). Thus, \(\vert g(C_u)\vert=\vert g(B_u)\vert\). By taking \(p=x\), we see that \(1\in L(\{C_u\}_{u\in V(G)})\).
(b) Note that the restriction of \(f\) to \(\{1,2,\dots, c\}\cup (\mathbb N\setminus \{1,2,\dots, d-1\})\) is injective. This implies that \(f(B_u)\cap f(B_v)=f(B_u\cap B_v)\) for all \(u,v\in V(G)\). Thus, \(\vert C_u\cap C_v\vert=\vert B_u\cap B_v\vert\). Therefore, \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\) and \(c,c+1\in L(\{C_u\}_{u\in V(G)})\). Now, \(c+1,c+2,\dots, d-1\notin L(\{B_u\}_{u\in V(G)})\) imply that
if \(d\in B_{u_1}\) for some \(u_1\in V(G)\), then \(d\) is the initial point of a consecutive part of \(g(B_{u_1})\);
if \(c\in B_{u_2}\) for some \(u_2\in V(G)\), then \(c\) is the terminal initial point of a consecutive part of \(g(B_{u_2})\).
Therefore, for each \(u\in V(G)\), either
\(g(B_u)=\{X_1,X_2,\dots, X_{m}\}\) and \(c,d\notin B_u\), or
\(g(B_u)=\{X_1,X_2,\dots,X_{i_0},X_{i_0+1},\dots, X_{m}\}\), \(c\notin B_u\) and \(d\) is the initial point in \(X_{i_0+1}\), or
\(g(B_u)=\{X_1,X_2,\dots,X_{i_0},X_{i_0+1},\dots, X_{m}\}\), \(d\notin B_u\) and \(c\) is the terminal point in \(X_{i_0}\), or
\(g(B_u)=\{X_1,X_2,\dots,X_{i_0},X_{i_0+1},\dots, X_{m}\}\), \(c\) is the terminal point in \(X_{i_0}\) and \(d\) is the initial point in \(X_{i_0+1}\).
If (1), (2) or (3) holds, then \(\vert g(C_u)\vert=\vert g(B_u)\vert\). If (4) holds, then \(\vert g(C_u)\vert=\vert g(B_u)\vert-1\). In fact, \[\begin{aligned} g(C_u)=\{X_1,X_2,\dots,X_{i_0-1},(X_{i_0}\cup X_{i_0+1}'),X_{i_0+2}'\dots, X_{m}'\}, \end{aligned}\] where \(X_i'=X_{i}-d+c+1\). Hence, \(\vert g(C_u)\vert\leq \vert g(B_u)\vert\) for all \(u\in V(G)\).
(c) Since \(c\) is not an element in \(B_u\cap B_v\) for all \(u,v\in V(G)\) with \(u\neq v\), we have \(C_u\cap C_v=B_u\cap B_v\). Hence, \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\). \(\square\)
Lemma 3.7. Let \(G=\mathfrak F(\{B_u\}_{u\in V(G)})\) for some \(\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\). Then there exists \(\{C_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\) such that \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\) and \(\vert g(C_u)\vert\leq \vert g(B_u)\vert\) and \(\vert C_u\cap C_v\vert=\vert B_u\cap B_v\vert\) for all \(u,v\in V(G)\) with \(u\neq v\). Furthermore, \(L(\{C_u\}_{u\in V(G)})=\{1,2,\dots, m\}\) and each \(i\in \{1,2,\dots, m\}\) is contained in at least two \(C_u\)’s.
Proof. Suppose \(c\in B_{u_0}\) for exactly one \(u_0\in V(G)\). By part (c) of Lemma 3.6, \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\) where \(C_{u_0}=B_{u_0}\setminus \{c\}\) and \(C_u=B_u\) for all \(u\in V(G)\setminus \{c\}\). By Lemma 2.5, \(\vert g(C_{u_0})\vert=\vert g(B_{u_0})\vert+1\) if \(c\) is a middle point of a consecutive part of \(g(B_0)\) and \(\vert g(C_{u_0})\vert=\vert g(B_{u_0})\vert\), otherwise. If \(\vert g(C_{u_0})\vert=\vert g(B_{u_0})\vert+1\), then \(c-1,c+1\in C_{u_0}\). By taking \[\begin{aligned} f(a)=\begin{cases} a, & \text{for $1\leq a\leq c$};\\ a-1,\qquad\vphantom{i} & \text{for $a\geq c+1$}, \end{cases} \end{aligned}\] in part (b) of Lemma 3.6, we can close the gap. In fact, if \(C'_u=f(C_u)=\{ f(a)\ :\ a\in C_u\}\) for all \(u\in V(G)\), then \(G=\mathfrak F(\{C_u'\}_{u\in V(G)})\) and \(c,c+1\in L(\{C_u'\}_{u\in V(G)})\). Furthermore, for all \(u,v\in V(G)\) with \(u\neq v\), \(\vert g(C_u')\vert= \vert g(C_u)\vert=\vert g(B_u)\vert\) for \(u\neq u_0\) and \(\vert g(C_{u_0}')\vert= \vert g(C_{u_0})\vert-1=\vert g(B_{u_0})\vert\). Similarly, we can close the gap for the case \(\vert g(C_{u_0})\vert=\vert g(B_{u_0})\vert\).
If there is a gap like in the hypothesis of part (b) of Lemma 3.6, we can close the gap like in the conclusion of part (b) the lemma. If \(1\notin L(\{B_u\}_{u\in V(G)})\), we can apply part (a) of Lemma 3.6. Therefore, after finite number of steps, we will obtain \(\{C_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\) for which \(L(\{C_u\}_{u\in V(G)})=\{1,2,\dots, m\}\) and other conclusions of the lemma also hold. \(\square\)
Given a graph \(G\), we shall label its edges with an element in \(\mathbb N\). If an edge \(uv\) is labelled with \(a\in \mathbb N\), we set \(E_{uv}=\{a\}\). Note that \(E_{uv}=E_{vu}\) as \(uv=vu\) is the same edge. The set \(\{E_{uv}\}_{u\sim_Gv}\) is called an edge labelling of \(G\). For each \(u\in V(G)\), let \(N_G(u)=\{v\in V(G)\ : v\sim_G u\}\) be the neighbourhood of \(u\) and \[\begin{aligned} C_u=\bigcup_{v\in N_G(u)} E_{uv}. \end{aligned}\]
The edge labelling \(\{E_{uv}\}_{u\sim_Gv}\) is said to be \(\mathcal T_2\)-compatible if \[\begin{aligned} C_u\cap C_v=\begin{cases} E_{uv}, \qquad\vphantom{i} &\text{for all $u\sim_Gv$};\\ \varnothing, &\text{otherwise}. \end{cases} \end{aligned}\]
Lemma 3.8. Let \(G\) be a graph.
Suppose \(G=\mathfrak F(\{B_u\}_{u\in V(G)})\) for some \(\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\) and \(\vert B_u\cap B_v\vert\leq 1\) for all \(u,v\in V(G)\) with \(u\neq v\). Let \(E_{uv}=B_u\cap B_v\) for all \(u\sim_Gv\). Then, \(\{E_{uv}\}_{u\sim_Gv}\) is a \(\mathcal T_2\)-compatible edge labelling of \(G\).
Suppose \(\{E_{uv}\}_{u\sim_Gv}\) is a \(\mathcal T_2\)-compatible edge labelling of \(G\). If \(C_u=\bigcup_{v\in N_G(u)} E_{uv}\) for all \(u\in V(G)\), then \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\in\mathcal T_2\).
Proof. Note that \(E_{uv}\) is an one element set for all \(u\sim_Gv\). Let \(C_u=\bigcup_{v\in N_G(u)} E_{uv}\). Since \(E_{uv}\subseteq B_u\) for all \(u\sim_Gv\), we have \(C_u\subseteq B_u\). Therefore, \(C_u\cap C_v\subseteq B_u\cap B_v\) for all \(u,v\in V(G)\). This means if \(u\nsim_Gv\), then \(C_u\cap C_v=\varnothing\). On the other hand, if \(u\sim_Gv\), then \(E_{uv}=B_u\cap B_v\neq\varnothing\). Now \(E_{uv}\subseteq C_u\) and \(E_{uv}=E_{vu}\subseteq C_v\) imply that \(C_u\cap C_v=E_{uv}\). Hence, \(\{E_{uv}\}_{u\sim_Gv}\) is \(\mathcal T_2\)-compatible.
Suppose \(\{E_{uv}\}_{u\sim_Gv}\) is \(\mathcal T_2\)-compatible. Then \(\{C_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\) and \(\vert C_u\cap C_v\vert\leq 1\) for all \(u,v\in V(G)\) with \(u\neq v\). By \(\mathcal T_2\)-compatibility, \(C_u\cap C_v\neq \varnothing\) if and only if \(u\) is adjacent to \(v\). Hence, \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\in\mathcal T_2\). \(\square\)
The following corollary is a consequence of Lemma 3.8.
Corollary 3.9. \(G\in \mathcal T_2\) if and only if there exists a \(\mathcal T_2\)-compatible edge labelling of \(G\).
For \(1\leq i\leq n\), \(1\leq j\leq m_i\) let \(H_i\) and \(Q_{ij}\) be complete graphs. Let \(G'\) be the union of these complete graphs, i.e., \[G'=\bigcup_{1\leq i\leq n} H_i\cup \bigcup_{\substack {1\leq i\leq n,\\ 1\leq j\leq m_i}} Q_{ij}.\]
Let \(x_i\in V(H_i)\). Since \(V(H_i)\cap V(H_{i'})=\varnothing\) for \(i\neq i'\), we have \(x_{i}\neq x_{i'}\). For each \(u\in V(Q_{ij})\) add an edge \(x_iu\) to the graph \(G'\). For each \(u\in V(H_{i+1})\) add an edge \(x_iu\) to the graph \(G'\). Let \(G\) denotes the resulting graph. Note that \(G\) is connected, \(G[\{x_i\}\cup V(Q_{ij})]\) and \(G[\{x_i\}\cup V(H_{i+1})]\) are complete graphs. Furthermore, \[\begin{aligned} E(G)=E(G')\cup \bigcup_{\substack {1\leq i\leq n,\\ 1\leq j\leq m_i}} \{x_iu\ :\ u\in V(Q_{ij})\}\cup \bigcup_{\substack {1\leq i\leq n-1}} \{x_iu\ :\ u\in V(H_{i+1})\}. \end{aligned}\]
The class of graphs formed this way is denoted by \(\mathcal H\).
Theorem 3.10. Let \(G\) be a connected graph. Then, \(i_{\mathcal T_2}(G)=1\) if and only if \(G\in\mathcal H\).
Proof. Suppose \(G\in\mathcal H\). Now, we shall construct a \(\mathcal T_2\)-compatible edge labelling for \(G\).
Label all edges in \(H_1\) with 1.
For \(2\leq i\leq n\), label all edges in \(H_i\) with \(m_1+m_2+\cdots +m_{i-1}+i\).
For \(1\leq i\leq n-1\), label all edges in \(\{x_iu\ :\ u\in V(H_{i+1})\}\) with \(m_1+m_2+\cdots +m_{i}+i+1\).
For \(1\leq i\leq n\) and \(1\leq j\leq m_i\), label all edges in \(Q_{ij}\) with \(m_1+m_2+\cdots +m_{i-1}+i+j\).
For \(1\leq i\leq n\) and \(1\leq j\leq m_i\), label all edges in \(\{x_iu\ :\ u\in V(Q_{ij})\}\) with \(m_1+m_2+\cdots +m_{i-1}+i+j\).
For each \(u\in V(G)\), let \(C_u=\bigcup_{v\in N_G(u)} E_{uv}\). We shall show that \(\{E_{uv}\}_{u\sim_Gv}\) is \(\mathcal T_2\)-compatible. Suppose \(C_{u_1}\cap C_{v_1}\neq\varnothing\) for some none adjacent vertices \(u_1,v_1\). Let \(y\in C_{u_1}\cap C_{v_1}\). Then \(E_{u_1z_1}= E_{v_1z_2}=\{y\}\) for some vertices \(z_1\) and \(z_2\) such that \(u_1\sim_G z_1\) and \(v_1\sim_G z_2\). If \(u_1z_1\) is an edge in \(H_i\), then \(y= m_1+m_2+\cdots +m_{i-1}+i\). Therefore, \(v_1z_2\) is an edge in \(H_i\) or it is an edge in \(\{x_{i-1}u\ :\ u\in V(H_{i})\}\). In either case, \(u_1\) is adjacent to \(v_1\), a contradiction. If \(u_1z_1\) is an edge in \(Q_{ij}\), then \(y=m_1+m_2+\cdots +m_{i-1}+i+j\). Therefore, \(v_1z_2\) is an edge in \(Q_{ij}\) or it is an edge in \(\{x_iu\ :\ u\in V(Q_{ij})\}\). In either case, \(u_1\) is adjacent to \(v_1\), a contradiction. Similarly, if \(u_1z_1\) is an edge in \(\{x_iu\ :\ u\in V(H_{i+1})\}\) or it is an edge in \(\{x_iu\ :\ u\in V(Q_{ij})\}\), we also will obtain the conclusion that \(u_1\) is adjacent to \(v_1\). Hence, \(C_{u}\cap C_{v}=\varnothing\) for \(u\) not adjacent to \(v\).
Suppose \(u\) is adjacent to \(v\). Clearly, \(E_{uv}\subseteq C_u\cap C_v\). Suppose \(E_{uv}\subsetneq C_u\cap C_v\). Let \(y\in (C_{u}\cap C_{v})\setminus E_{uv}\). Then \(E_{uz_1}= E_{vz_2}=\{y\}\) for some vertices \(z_1\) and \(z_2\) such that \(u\sim_G z_1\) and \(v\sim_G z_2\). Let \(E_{uv}=\{y_0\}\). Then, \(y\neq y_0\). If \(uz_1\) is an edge in \(H_i\), then \(y= m_1+m_2+\cdots +m_{i-1}+i\). Therefore, \(vz_2\) is an edge in \(H_i\) or it is an edge in \(\{x_{i-1}z\ :\ z\in V(H_{i})\}\). If \(v\in V(H_i)\), then \(uv\) is labelled with \(y\). Thus, \(y_0=y\), a contradiction. So, \(v=x_{i-1}\) and \(z_2\in V(H_i)\). However, \(x_{i-1}\) is adjacent to all vertices in \(H_i\). By construction, \(x_{i-1}u\) is labelled with \(y\). This implies that \(y_0=y\), a contradiction. If \(uz_1\) is an edge in \(Q_{ij}\), then \(y=m_1+m_2+\cdots +m_{i-1}+i+j\). Therefore, \(vz_2\) is an edge in \(Q_{ij}\) or it is an edge in \(\{x_iz\ :\ z\in V(Q_{ij})\}\). In either case, \(uv\) is labelled with \(y\) too, a contradiction. Similarly, if \(uz_1\) is an edge in \(\{x_iz\ :\ z\in V(H_{i+1})\}\) or it is an edge in \(\{x_iz\ :\ z\in V(Q_{ij})\}\), we also will obtain the conclusion that \(uv\) is labelled with \(y\). Hence, \(E_{uv}= C_u\cap C_v\) for \(u\) adjacent to \(v\).
We have shown that \(\{E_{uv}\}_{u\sim_Gv}\) is \(\mathcal T_2\)-compatible. By part (b) of Lemma 3.8, \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\). Now, for all \(1\leq i\leq n\) and \(1\leq j\leq m_i\), \[\begin{aligned} C_{x_i} =&\{m_1+m_2+\cdots +m_{i-1}+i, m_1+m_2+\cdots +m_{i-1}+i+1,\dots,\\ & m_1+m_2+\cdots +m_{i-1}+i+m_i, m_1+m_2+\cdots +m_{i-1}+m_{i}+i+1\};\\ C_{u} =&\{m_1+m_2+\cdots +m_{i-1}+i\}, \qquad \text{for all $u\in H_i\setminus \{x_i\}$};\\ C_{u} =&\{m_1+m_2+\cdots +m_{i-1}+i+j\}, \qquad \text{for all $u\in Q_{ij}$}. \end{aligned}\]
Hence, \(\vert g(C_u)\vert=1\) for all \(u\in V(G)\) and \(i_{\mathcal T_2}(G)=1\).
Suppose \(i_{\mathcal T_2}(G)=1\). Then there exists \(\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}(1)\) and \(\vert B_u\cap B_v\vert\leq 1\) for all \(u,v\in V(G)\) with \(u\neq v\) such that \(G=\mathfrak F(\{B_u\}_{u\in V(G)})\). By Lemma 3.7, we may assume that \(L(\{B_u\}_{u\in V(G)})=\{1,2,\dots, l\}\) and each \(i\in \{1,2,\dots, l\}\) is contained in at least two \(B_u\)’s. Let \(Y_i=\{u\in V(G)\ :\ i\in B_u\}\) for \(1\leq i\leq l\). Note that \(H_1=G[Y_1]\) is a complete graph. If \(G=H_1\), then \(G\in\mathcal H\). Suppose \(G\neq H_1\). Since \(G\) is connected, there is a \(x_1\in V(H_1)\) with \(\vert B_{x_1}\vert\geq 2\). Let \(B_{x_1}=\{1,2,\dots, m_1+2\}\). Note that \(B_u=\{1\}\) for other \(u\in V(H_1)\setminus \{x_1\}\), otherwise, we have \(\vert B_u\cap B_{x_1}\vert\geq 2\) or \(\vert g(B_u)\vert\geq 2\). For \(1\leq j\leq m_1\), set \(Q_{1j}=G[Y_{j+1}\setminus \{x_1\}]\). Let \(H_2=G[Y_{m_1+2}\setminus \{x_1\}]\). If \(m_1+2=l\), then we see that \(G\in\mathcal H\). Suppose \(l>m_1+2\). Since \(G\) is connected, there is a \(x_2\in V(H_2)\) with \(\vert B_{x_2}\vert\geq 2\). Let \(B_{x_2}=\{m_1+2,m_1+3,\dots, m_1+m_2+3\}\). Note that \(B_u=\{m_1+2\}\) for other \(u\in V(H_2)\setminus \{x_2\}\), otherwise, we have \(\vert B_{u}\cap B_{x_1}\vert\geq 2\), \(\vert B_u\cap B_{x_2}\vert\geq 2\) or \(\vert g(B_u)\vert\geq 2\). For \(1\leq j\leq m_2\), set \(Q_{2j}=G[Y_{j+m_1+2}\setminus \{x_2\}]\). Let \(H_3=G[Y_{m_1+m_2+3}\setminus \{x_2\}]\). If \(m_1+m_2+3=l\), then we see that \(G\in\mathcal H\). If \(l>m_1+m_2+3\), then we continue this process. Eventually, we will have \(G\in\mathcal H\).
This completes the proof of the theorem. \(\square\)
In this section, we will prove Theorem 4.8. We begin with the following lemmas.
Lemma 4.1. Suppose \(\{E_{uv}\}_{u\sim_Gv}\) is a \(\mathcal T_2\)-compatible edge labelling of \(G\). If \(E_{u_1v_1}=E_{u_2v_2}=\{c\}\) and \(u_1\neq u_2\), then \(u_1\) is adjacent to \(u_2\) and \(E_{u_1u_2}=\{c\}\).
Proof. For each \(u\in V(G)\), let \(C_u=\bigcup_{v\in N_G(u)} E_{uv}\). Now \(c\in C_{u_1}\cap C_{u_2}\) implies that \(C_{u_1}\cap C_{u_2}\neq\varnothing\). Thus, \(u_1\) and \(u_2\) are adjacent. By \(\mathcal T_2\)-compatibility, \(\{c\}= C_{u_1}\cap C_{u_2}=E_{u_1u_2}\). \(\square\)
Lemma 4.2. Suppose \(\{E_{uv}\}_{u\sim_Gv}\) is a \(\mathcal T_2\)-compatible edge labelling of \(G\). If \(H\) is a subgraph of \(G\), then \(\{E_{uv}\}_{u\sim_Hv}\) is a \(\mathcal T_2\)-compatible edge labelling of \(H\).
Proof. For each \(u\in V(G)\), let \(B_u=\bigcup_{v\in N_G(u)} E_{uv}\). For each \(u\in V(H)\), let \(C_u=\bigcup_{v\in N_H(u)} E_{uv}\). Since \(u\sim_H v\) implies that \(u\sim_G v\), \(C_u\subseteq B_u\). Therefore \(C_u\cap C_v\subseteq B_u\cap B_v\) for all \(u,v\in V(H)\) with \(u\neq v\). So, if \(B_u\cap B_v=\varnothing\), then \(C_u\cap C_v=\varnothing\).
Next, if \(u\sim_H v\), then \(u\sim_G v\). This means \(B_u\cap B_v=E_{uv}\). Since \(u,v\) are vertices in \(H\), \(E_{uv}\subseteq C_u\cap C_v\). Hence, \(C_u\cap C_v=E_{uv}\) and \(\{E_{uv}\}_{u\sim_Hv}\) is a \(\mathcal T_2\)-compatible edge labelling of \(H\). \(\square\)
Lemma 4.3. Let \(G'\) be a graph and \(u_0,v_0\in V(G')\) such that \(u_0\neq v_0\). Suppose
\(G'=\mathfrak F(\{B_u\}_{u\in V(G')})\) for some \(\{B_u\}_{u\in V(G')}\subseteq 2^{\mathbb N}_{0}\) and \(\vert B_u\cap B_v\vert\leq 1\) for all \(u,v\in V(G')\) with \(u\neq v\);
\(c\in B_{u_0}\cap B_{v_0}\) and \(c\notin B_u\) for all \(u\in V(G')\setminus \{u_0,v_0\}\).
Let \(G\) be a graph obtained from \(G'\) by deleting the edge \(u_0v_0\). Then, there exists \(\{C_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\) such that \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\), \(\vert C_u\cap C_v\vert\leq 1\) for all \(u,v\in V(G)\) with \(u\neq v\), \(\vert g(C_u)\vert=\vert g(B_u)\vert\) for all \(u\in V(G)\).
Proof. Let \(D_u=B_u\) for all \(u\in V(G)\), \(D_{u_0}=B_{u_0}\setminus \{c\}\) and \(D_{v_0}=B_{v_0}\setminus \{c\}\). Then, \(D_u\cap D_v=B_u\cap B_v\) for all \(u,v\in V(G)\setminus \{u_0,v_0\}\). Let \(v\notin \{ u_0,v_0\}\). Clearly, \(D_{u_0}\cap D_v\subseteq B_{u_0}\cap B_v\). If \(u_0\not\sim_G v\), then \(u_0\not\sim_{G'} v\) and \(B_{u_0}\cap B_v=\varnothing\). This means \(D_{u_0}\cap D_v=\varnothing\). If \(u_0\sim_G v\), then \(u_0\sim_{G'} v\) and \(B_{u_0}\cap B_v=\{d\}\) for some \(d\in\mathbb N\). Since \(d\neq c\), we have \(d\in D_{u_0}=B_{u_0}\setminus \{c\}\). Hence, \(D_{u_0}\cap D_v=\{d\}\). In either case, \(D_{u_0}\cap D_v= B_{u_0}\cap B_v\). Similarly, \(D_{v_0}\cap D_v= B_{v_0}\cap B_v\) for \(v\notin \{ u_0,v_0\}\). Finally, we have \(D_{u_0}\cap D_{v_0}=\varnothing\). Thus, \(G=\mathfrak F(\{D_u\}_{u\in V(G)})\). Furthermore, \(\vert g(D_u)\vert=\vert g(B_u)\vert\) for all \(u\in V(G)\setminus\{u_0,v_0\}\). Let \(x\in \{u_0,v_0\}\). Note that if \(c\) is the initial point or the terminal point of a consecutive part of \(g(B_{x})\), then \(\vert g(D_x)\vert=\vert g(B_x)\vert\).
Let \(\{x,y\}=\{u_0,v_0\}\). Suppose \(c\) is the initial point of a consecutive part of \(g(B_{x})\) and \(c\) is a middle point of a consecutive part of \(g(B_{y})\). Then, \(\vert g(D_x)\vert=\vert g(B_x)\vert\) and \(\vert g(D_y)\vert=\vert g(B_y)\vert+1\) and \(c-1,c+1\in D_y\). By part (b) of Lemma 3.6, there exists \(\{C_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\) such that \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\) and \(\vert C_u\cap C_v\vert\leq 1\) for all \(u,v\in V(G)\) with \(u\neq v\). Furthermore, \(\vert g(C_u)\vert=\vert g(D_u)\vert=\vert g(B_u)\vert\) for all \(u\in V(G)\setminus \{y\}\) and \(\vert g(C_y)\vert=\vert g(D_y)\vert-1=\vert g(B_y)\vert\).
Similarly, the same conclusions hold if
\(c\) is the terminal point of a consecutive part of \(g(B_{x})\) and \(c\) is a middle point of a consecutive part of \(g(B_{y})\); or
\(c\) is a middle point of a consecutive part of \(g(B_{x})\) and \(c\) is a middle point of a consecutive part of \(g(B_{y})\).
This completes the proof of the lemma. \(\square\)
Lemma 4.4. Let \(G'\) be a graph and \(u_0\in V(G')\). Let \(G\) be a graph obtained from \(G'\) by deleting the vertex \(u_0\) and all edges in incident to it. Then, \[\begin{aligned} i_{\mathcal T_2}(G)\leq i_{\mathcal T_2}(G')\leq i_{\mathcal T_2}(G)+1. \end{aligned}\]
Proof. Firstly, we will prove \(i_{\mathcal T_2}(G)\leq i_{\mathcal T_2}(G')\). Let \(i_{\mathcal T_2}(G')=k\). Then \(G'=\mathfrak F(\{B_u\}_{u\in V(G')})\) for some \(\{B_u\}_{u\in V(G')}\subseteq 2^{\mathbb N}_{0}(k)\) and \(\vert B_u\cap B_v\vert\leq 1\) for all \(u,v\in V(G')\) with \(u\neq v\). By Lemma 3.7, we may assume that \(L(\{B_u\}_{u\in V(G')})=\{1,2,\dots, m\}\) and each \(i\in \{1,2,\dots, m\}\) is contained in at least two \(B_u\)’s. Let \(E_{uv}=B_u\cap B_v\) for all \(u\sim_{G'}v\). By part (a) of Lemma 3.8, \(\{E_{uv}\}_{u\sim_{G'}v}\) is a \(\mathcal T_2\)-compatible edge labelling of \(G'\). Since \(E_{uv}\subseteq B_u\) for all \(u\sim_{G'}v\), \(\bigcup_{v\in N_{G'}(u)} E_{uv}\subseteq B_u\). On the other hand, let \(y\in B_u\). There is a \(v'\in V(G')\) with \(y\in B_{v'}\). Therefore, \(u\) is adjacent to \(v'\) and \(y\in B_u\cap B_{v'}=E_{uv'}\). Hence, \(y\in \bigcup_{v\in N_{G'}(u)} E_{uv}\) and \(B_u= \bigcup_{v\in N_{G'}(u)} E_{uv}\). Note that \(\vert g(B_u)\vert\leq k\) for all \(u\in V(G')\).
Suppose \(c\in B_{u_0}\cap B_{v_0}\) and \(c\notin B_u\) for all \(u\in V(G')\setminus \{u_0,v_0\}\). Let \(G'_1\) be the graph obtained from \(G'\) by removing the edge \(u_0v_0\) forom \(G'\). By Lemma 4.3, there exists \(\{D_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\) such that \(G=\mathfrak F(\{D_u\}_{u\in V(G)})\), \(\vert D_u\cap D_v\vert\leq 1\) for all \(u,v\in V(G)\) with \(u\neq v\), \(\vert g(D_u)\vert=\vert g(B_u)\vert\) for all \(u\in V(G)\). Thus, \(i_{\mathcal T_2}(G'_1)\leq i_{\mathcal T_2}(G')\). We can apply Lemma 4.3 again to remove an edge connecting a vertex in \(G_1'\) to \(u_0\) whenever condition (b) of Lemma 4.3 is satisfied. Therefore, we may as well assume that condition (b) of Lemma 4.3 is not satisfied for the original graph \(G'\). To be precise, let \(v_1,v_2,\dots, v_l\) be the only vertices in \(G'\) adjacent to \(u_0\). Then, for each \(i\), there exists an edge \(u'v'\) in \(G'\) such that \(u'v'\neq u_0v_i\) and \(E_{u'v'}=E_{u_0v_i}\).
By Lemma 4.2, \(\{E_{uv}\}_{u\sim_{G}v}\) is a \(\mathcal T_2\)-compatible edge labelling of \(G\). Note that \(v_1,v_2,\dots, v_l\) are vertices of \(G\). Let \(C_u= \bigcup_{v\in N_G(u)} E_{uv}\). Then, \(C_u= B_u\) for all \(u\in V(G)\setminus \{v_1,v_2,\dots, v_l\}\) and \(C_{v_i}\subseteq B_{v_i}\) for all \(i\). Therefore, \(\vert g(C_u)\vert=\vert g(B_u)\vert\) for all \(u\in V(G)\setminus \{v_1,v_2,\dots, v_l\}\). Let \(i\in \{1,2,\dots, l\}\) be fixed and \(E_{u_0v_i}=\{c\}\). Note that either \(C_{v_i}=B_{v_i}\) or \(C_{v_i}=B_{v_i}\setminus \{c\}\). We shall show that the latter cannot occur.
Recall that there exists an edge \(u'v'\) in \(G'\) such that \(u'v'\neq u_0v_i\) and \(E_{u'v'}=E_{u_0v_i}\). Note that \(u'\) and \(v'\) cannot be both equal to \(u_0\). So, by Lemma 4.1, \(u_0\) is adjacent to \(u'\) or \(v'\). Suppose \(u_0\) is adjacent to \(u'\). If \(u'=v_i\), then \(v'\neq u_0\), for \(u'v'\) and \(u_0v_i\) are different edges. So, \(u_0\) is adjacent to \(v'\) and \(v'\neq v_i\). Similarly, if \(u_0\) is adjacent to \(v'\) and \(v'=v_i\), we will get \(u_0\) is adjacent to \(u'\) and \(u'\neq v_i\). Therefore, we may as well assume that \(u_0\) is adjacent to \(u'\) and \(u'\neq v_i\). This implies that \(u'=v_j\) for some \(j\neq i\). So, \(E_{u_0v_i}=\{c\}=E_{u_0v_j}\). Again, by Lemma 4.1, \(v_i\) is adjacent to \(v_j\) and \(E_{v_iv_j}=\{c\}\). This implies that \(c\in C_{v_i}\) and \(C_{v_i}=B_{v_i}\). Hence, \(C_{v_i}=B_{v_i}\) for all \(i\) and \(\vert g(C_u)\vert=\vert g(B_u)\vert\) for all \(u\in V(G)\). This means \(i_{\mathcal T_2}(G)\leq k=i_{\mathcal T_2}(G')\).
Now, we shall prove \(i_{\mathcal T_2}(G')\leq i_{\mathcal T_2}(G)+1\). Let \(i_{\mathcal T_2}(G)=k\). Then, \(G=\mathfrak F(\{B_u\}_{u\in V(G)})\) for some \(\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}(k)\) and \(\vert B_u\cap B_v\vert\leq 1\) for all \(u,v\in V(G)\) with \(u\neq v\). Let \(\max L(\{B_u\}_{u\in V(G)})=m\). Then, \(x\notin L(\{B_u\}_{u\in V(G)})\) for any integer \(x\geq m+1\). Let \(v_1,v_2,\dots, v_l\) be the only vertices in \(G'\) adjacent to \(u_0\). Set \(C_{u_0}=\{m+1,m+2,\dots, m+l\}\), \(C_{v_i}=B_{v_i}\cup \{m+i\}\) for all \(i\) and \(C_u=B_u\) for all \(u\in V(G')\setminus \{u_0,v_1,v_2,\dots, v_l\}\). Then, \(G'=\mathfrak F(\{C_u\}_{u\in V(G')})\). By Lemma 2.4, \(\vert g(C_{v_i})\vert\leq \vert g(B_{v_i})\vert+1\) for all \(i\). Clearly, \(\vert g(C_{u_0})\vert=1\) and \(\vert g(C_{u})\vert\leq \vert g(B_{u})\vert\) for other \(u\in V(G')\setminus \{u_0,v_1,v_2,\dots, v_l\}\). Hence, \(i_{\mathcal T_2}(G')\leq k+1=i_{\mathcal T_2}(G)+1\). \(\square\)
Lemma 4.5. Let \(\{E_{uv}\}_{u\sim_Gv}\) be an edge labelling of \(G\). Suppose that if \(u_1v_1,u_2v_2,\dots, u_mv_m\) are distinct edges in \(G\) with \(E_{u_1v_1}=E_{u_2v_2}=\cdots =E_{u_mv_m}\) ,then
\(m=1\), or
\(m=3\) and the three edges \(u_1v_1\), \(u_2v_2\) and \(u_3v_3\) form a triangle (e.g. \(u_1=u_2\) and \(G[\{u_1,v_1,v_2\}]\) is a triangle).
Then, \(\{E_{uv}\}_{u\sim_Gv}\) is \(\mathcal T_2\)-compatible.
Proof. Let \(C_u= \bigcup_{v\in N_G(u)} E_{uv}\). Suppose \(u\not\sim_G v\). If \(C_u\cap C_v\neq \varnothing\), then there exist \(z_1,z_2\in V(G)\) and \(y\in\mathbb N\) such that \(E_{uz_1}=\{y\}=E_{vz_2}\). By condition (b), the edges \(uz_1\) and \(vz_2\) are parts of the edges of a triangle. So, \(u\) is adjacent to \(v\) as \(uv\) must be the remaining edge of the triangle. This contradicts the assumption \(u\not\sim_G v\). Hence, \(C_u\cap C_v=\varnothing\).
Suppose \(u\sim_G v\). Note that \(E_{uv}\subseteq C_u\cap C_v\). If \(E_{uv}\subsetneq C_u\cap C_v\), then there exist \(z_1,z_2\in V(G)\) and \(y\in\mathbb N\) such that \(y\notin E_{uv}\) and \(E_{uz_1}=\{y\}=E_{vz_2}\). By condition (b), the edges \(uz_1\) and \(vz_2\) are parts of the edges of a triangle. So, \(uv\) must be the remaining edge of the triangle. This implies that \(E_{uv}=\{y\}\), a contradiction. Hence, \(C_u\cap C_v=E_{uv}\) and \(\{E_{uv}\}_{u\sim_Gv}\) is \(\mathcal T_2\)-compatible. \(\square\)
A triangulation is a planar graph for which every face is a triangle. Note that if a graph is a triangulation, then there are exactly 3 vertices on the outer boundary of the planar graph and the subgraph induced by the three vertices is a triangle. We shall call the the outer boundary the outer triangle. All other triangles in the graph will be called inner triangle. A triangle in a planar graph is said to be non-empty if its interior contains at least one vertex. A 4-connected triangulation is a triangulation whose only non-empty triangle is the outer triangle.
Let \(G\) be a 4-connected triangulation with at least 4 vertices. Let \(x,y,z\) be the vertices on the outer triangle \(\bigtriangleup_{\text{out}}\). Note that there is a unique vertex \(u_x\) in the interior of \(\bigtriangleup_{\text{out}}\) such that \(u_x\) is adjacent to \(y\) and \(z\). In fact, if there are more than one vertices in the interior of \(\bigtriangleup_{\text{out}}\) that are adjacent to \(y\) and \(z\), then there is a non-empty inner triangle in which \(yz\) is an edge of this triangle. We shall call the unique vertex \(u_x\) the vertex opposing \(x\). The vertex \(u_y\) opposing \(y\) is defined to be the unique vertex in the interior of \(\bigtriangleup_{\text{out}}\) that is adjacent to \(x\) and \(z\). Finally, the vertex \(u_z\) opposing \(z\) is defined similarly. We need the following lemma (see also [10, Fig. 1] for an illustration).
Lemma 4.6. [11, Lemma 3.1] Let \(G\) be a 4-connected triangulation with outer triangle \(\bigtriangleup_{\text{out}}\) and \(V(\bigtriangleup_{\text{out}})=\{x,y,z\}\). Let \(u_x,u_y\) and \(u_z\) be the vertices opposing to \(x,y\) and \(z\), respectively. Then the inner edges of \(G\) can be partitioned into three forests \(F_x\), \(F_y\), \(F_z\) such that
\(F_x\) is a Hamiltonian path of \(G-\{y, z\}\) going from \(x\) to \(u_x\),
\(F_y\) is a spanning tree of \(G -\{x, z\}\),
\(F_z\) is a spanning forest of \(G- \{y\}\) consisting of two trees, one containing \(x\) and one containing \(z\).
In particular, when \(G=K_4\) the complete graph with 4 vertices, then \(u_x=u_y=u_z\), \(F_x=G[\{x,u_x\}]\) is just the path \(xu_x\), \(F_y=G[\{y,u_x\}]\) is just the path \(yu_x\) and \(F_z=G[\{x\}]\cup G[\{z,u_x\}]\) is the union of two graphs, one with a single vertex \(x\) and the other just the path \(zu_x\).
Remark 4.7. We note here that by conditions (b) and (c) of Lemma 4.6, \(xu_y\) is an edge of \(F_x\) and \(zu_y\) is an edge of \(F_z\).
Theorem 4.8. If \(G\) is a planar graph, then \(i_{\mathcal T_2}(G)\leq 3\).
Proof. Firstly, we will construct a triangulation \(G'\) in which \(G\) is a subgraph of \(G'\). If \(G'\) has an inner face which is not a triangle, then we put a vertex in the middle of the face and add edges connecting all the vertices on the boundary of the face to this newly added vertex. This process will partition this face into smaller faces in which each of the newly faces is a triangle. If the outer face is not a triangle, then we add a vertex in the outer face and add edges connecting all the vertices on the outer boundary of the graph to this newly added vertex. Let \(G'\) denote the resulting graph. It is not hard to see that \(G'\) is a triangulation. By Lemma 4.4, \(i_{\mathcal T_2}(G)\leq i_{\mathcal T_2}(G')\). Hence, we may as well assume that the original graph \(G\) is a triangulation.
Now, \(\{E_{uv}\}_{u\sim_Gv}\) will be called a partial graph labelling of \(G\) if each \(E_{uv}\) is an one element set or an empty set. Let \(C_u= D_u\cup \bigcup_{v\in N_G(u)} E_{uv}\). At the beginning all the \(E_{uv}\)’s and \(D_u\)’s are empty set. We will add a label to an edge one step at a time. In the next step, we will choose an unlabelled edge and label it. If the chosen edge is \(u_1v_1\), then \(E_{u_1v_1}\) will be changed from empty set to one element set. During this process, we might also change the labels of the edges that are labelled earlier. This means if \(E_{u_2v_2}=\{c\}\), then it may be changed to \(E_{u_2v_2}=\{d\}\) for some \(d\neq c\). So, \(\{E_{uv}\}_{u\sim_Gv}\) and all the \(C_u\)’s are changing throughout the process. At the end of each step, we require that
\(\{E_{uv}\}_{u\sim_Gv}\) satisfies the condition of Lemma 4.5,
\(\vert g(C_u)\vert\leq 3\) for all \(u\in V(G)\),
if \(u_1u_2u_3u_1\) is an empty triangle and all the three edges are labelled, then either \(E_{u_1u_2}=E_{u_1u_3}=E_{u_2u_3}\) or there is an edge \(u_{i_0}u_{j_0}\) such that \(E_{u_{i_0}u_{j_0}}\) is unique, i.e., \(E_{uv}\neq E_{u_{i_0}u_{j_0}}\) for all other edges \(uv\in E(G)\setminus \{u_{i_0}u_{j_0}\}\).
We also require conditions (iv) and (v) which we will state later. An element \(c\) is said to be special in \(C_u\) if it is the terminal point of a consecutive part of \(g(C_u)\) and if \(c\in C_v\) for some \(v\neq u\), then \(c\) is the initial point of a consecutive part of \(g(C_v)\). An element \(c\) is said to be extra special in \(C_u\) if it is the initial point of a consecutive part of \(g(C_u)\) and if \(c\in C_v\) for some \(v\neq u\), then \(c\) is the initial point of a consecutive part of \(g(C_v)\). We are ready to state conditions (iv) and (v):
for each \(u\in V(G)\), if \(C_u\) is non-empty, then it contains a special element,
if \(u_1u_2u_3u_1\) is an empty triangle and \(E_{u_1u_2}=E_{u_1u_3}=E_{u_2u_3}\neq \varnothing\), then there is a vertex \(u_{i_0}\) such that \(C_{u_{i_0}}\) contains an extra special element.
At the end, when all the edges have been labelled, i.e., \(E_{uv}\neq \varnothing\) for all \(u\sim_G v\), we see that \(\{E_{uv}\}_{u\sim_Gv}\) is a \(\mathcal T_2\)-compatible (Lemma 4.5). By part (b) of Lemma 3.8, \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\). Thus, by condition (ii), \(i_{\mathcal T_2}(G)\leq 3\). Conditions (iii), (iv) and (v) are needed for the purpose of induction. We note here that \(D_u\) could be empty set at the end. The reason \(D_u\) is not empty is because we need to have special and extra special elements for conditions (iv) and (v).
We shall prove by induction on \(\vert V(G)\vert\) that there is a graph labelling \(\{E_{uv}\}_{u\sim_Gv}\) of \(G\) and \(\{D_u\}_{u\in V(G)}\) that satisfy conditions (i), (ii), (iii), (iv) and (v). Since \(G\) is a triangulation, \(\vert V(G)\vert\geq 3\).
Suppose \(\vert V(G)\vert =3\). Then, \(G\) is a triangle with vertices \(x,y,z\). Now, let \(E_{xy}=\{1\}\), \(E_{yz}=\{2\}\) and \(E_{zx}=\{3\}\). Then, \(C_{x}=\{1,3\}\), \(C_{y}=\{1,2\}\) and \(C_{z}=\{2,3\}\). Note that \(g(C_x)=\{\{1\},\{3\}\}\), \(g(C_y)=\{\{1,2\}\}\) and \(g(C_z)=\{\{2,3\}\}\). Therefore, \(\vert g(C_x)\vert=2\) and \(\vert g(C_y)\vert=1=\vert g(C_z)\vert\). Next, \(xyzx\) is the only empty triangle and \(E_{xz}\) is unique. Thus, conditions (i), (ii) and (iii) are satisfied. Now, 1 is a special element in \(C_x\), 2 is a special element in \(C_y\) and 3 is a special element in \(C_z\). Hence, conditions (iii), (iv) and (v) are satisfied. Here all the \(D_u\)’s are empty set.
Suppose \(\vert V(G)\vert \geq 4\). Assume that for any graph \(G'\) with \(\vert V(G')\vert<\vert V(G)\vert\), there exist a graph labelling \(\{E_{uv}\}_{u\sim_{G'}v}\) of \(G'\) and \(\{D_u\}_{u\in V(G')}\) that satisfy conditions (i), (ii), (iii), (iv) and (v).
Let \(\bigtriangleup_{0}=G[\{x,y,z\}]\) be a non-empty triangle in \(G\) with inclusion-minimal interior among all non-empty triangles in \(G\). Let \(S\subseteq V(G)\) be the set of all vertices in the interior of \(\bigtriangleup_{0}\). By the choice of inclusion-minimality, \(G[S\cup \{x,y,z\}]\) is a 4-connected triangulation. Let \(G'=G-S\). Then, \(G'\) is a triangulation and \(\vert V(G')\vert<\vert V(G)\vert\). We remark here that if \(G\) is 4-connected, then \(G'=G[\{x,y,z\}]\) is the outer triangle of \(G\).
By induction, there exist a graph labelling \(\{E_{uv}\}_{u\sim_{G'}v}\) of \(G'\) and \(\{D_u\}_{u\in V(G')}\) that satisfy conditions (i), (ii), (iii), (iv) and (v). For \(u\sim_Gv\) but \(u\not\sim_{G'}v\), we set \(E_{uv}=\varnothing\). Now, \(\{E_{uv}\}_{u\sim_{G}v}\) is a partial graph labelling of \(G\). In fact, all edges are labelled except those edges in the interior of \(\bigtriangleup_{0}\). We shall proceed to label those edges based on the decomposition of edges in Lemma 4.6. Let the inner edges of \(G_1=G[S\cup \{x,y,z\}]\) be partitioned into three forests \(F_x\), \(F_y\), \(F_z\) as in Lemma 4.6.
Now, \(xyzx\) is an empty triangle in \(G'\). By condition (iii), either all edges of \(\bigtriangleup_{0}\) are labelled with the same element or there is an uniquely labelled edge of \(\bigtriangleup_{0}\) in \(G'\). By condition (v), if all edges are labelled with the same element, then \(C_p\) has an extra special element for some \(p\in \{x,y,z\}\). We distinguish these two cases. In fact, by relabelling if necessary, we may assume that either
\(E_{xz}\) is unique in \(G'\), or
\(E_{xy}=E_{yz}=E_{xz}\) and \(C_{x}\) contains an extra special element.
Case 1. \(E_{xz}\) is unique in \(G'\).
Case 1.1. Suppose \(\vert S\vert=1\). This means \(G[S\cup \{x,y,z\}]=K_4\) and \(u_x=u_y=u_z=w\). Since \(y\in V(G')\), there is a special element, say \(d_0\) in \(C_y\). Now, change all the labels of the labelled edges according to the following rules: if \(c<d_0\), then \(c\) remains the same; and if \(c\geq d_0\), then \(c\) is changed to \(c+1\). After that label the edge \(yw\) with \(d_0\), i.e., \(E_{yw}=\{d_0\}\). When we change \(d_0\) to \(d_0+1\), the element \(d_0\) was removed from \(C_y\), however, after we labelled the edge \(yw\), \(d_0\) is added back in \(C_y\). Furthermore, \(\vert g(C_y)\vert\) remains the same before and after the changes. In fact, if \(\{a_1,a_2,\dots,a_l=d_0\}\) was a consecutive part of \(g(C_y)\) before the changes, then \(\{a_1,a_2,\dots,a_l,d_0+1\}\) is a consecutive part of \(g(C_y)\) after the changes. If \(X\) was a consecutive part of \(g(C_y)\) before the changes and the terminal point of \(X\) was smaller than \(a_1\), then \(X\) is a consecutive part of \(g(C_y)\) after the changes. If \(X\) was a consecutive part of \(g(C_y)\) before the changes and the initial point of \(X\) was greater than \(a_l=d_0\), then \(X+1\) is a consecutive part of \(g(C_y)\) after the changes. The same is true for other \(g(C_u)\), \(u\in V(G')\setminus \{y\}\) because either \(d_0\notin C_u\) or \(d_0\) is an initial point of a consecutive part of \(g(C_u)\). Note that if \(b\) was a special element of \(C_u\) for some \(u\in V(G)\) and \(b<d_0\) before the changes, then \(b\) is a special element of \(C_u\) after the changes. Also, if \(b\) was a special element of \(C_u\) for some \(u\in V(G)\) and \(b\geq d_0\) before the changes, then \(b+1\) is a special element of \(C_u\) after the changes. Similarly, if \(C_u\) contained an extra special element, then after the changes, it still contains an extra special element. Note that if \(E_{xz}=\{a_0\}\) and \(a_0<d_0\) before the changes, then \(E_{xz}=\{a_0\}\) after the changes and it is still unique, and if \(E_{xz}=\{a_0\}\) and \(a_0\geq d_0\) before the changes, then \(E_{xz}=\{a_0+1\}\) after the changes and it is still unique. We set \(E_{xw}=E_{zw}=E_{xz}\). At the moment \(\vert g(C_w)\vert=2\). Now, we choose an integer \(b_0\in\mathbb N\) such that \(b_0\notin \bigcup_{uv\in E(G)} E_{uv}\) and set \(D_w=\{b_0\}\). Then, \(\vert g(C_w)\vert\leq 3\) and all other \(\vert g(C_u)\vert\) remains the same. Note that \(b_0\) is both a special and an extra special element in \(C_w\). The empty triangles in \(G'\) satisfy condition (iii). Now, there are three empty triangles, \(xwzx\), \(xywx\) and \(yzwy\) in the interior of \(\bigtriangleup_{0}\). For the empty triangle \(yzwy\), \(E_{yw}=\{d_0\}\) is unique whereas for the empty triangle \(xywx\), \(E_{yw}=\{d_0\}\) is unique. For the triangle \(xwzx\), \(E_{xz}=E_{xw}=E_{zw}\) and \(b_0\) is both a special and an extra special element in \(C_w\). Thus, conditions (iii) and (v) are satisfied. In fact, it is not hard to see that conditions (i) to (v) are satisfied.
Case 1.2. Suppose \(\vert S\vert\geq 2\). Choose a \(n_0\in\mathbb N\) such that for all \(c\geq n_0\), \(c\notin \bigcup_{uv\in E(G')} E_{uv}\). In fact, we may choose \(n_0\) to be an integer greater than all other integers in \(\bigcup_{uv\in E(G')} E_{uv}\). Now, \(F_x\) is a Hamiltonian path of \(G_1-\{y, z\}\) going from \(x\) to \(u_x\). Recall that \(xu_y\) is an edge in \(F_x\) (Remark 4.7). Therefore, the Hamiltonian path is from \(x\) to \(u_y\) and then from \(u_y\) to \(u_x\). Let the path from \(u_y=v_1\) to \(u_x=v_{s}\) be \(v_1v_2\dots v_s\). Note that \(S=\{u_y=v_1,v_2,\dots, v_s=u_x\}\) and \(s\geq 2\). Now, for \(1\leq i\leq s-1\), we set \(E_{v_iv_{i+1}}=\{n_0+i\}\). At this moment, conditions (i) to (v) are satisfied. In fact, \(\vert g(C_u) \vert=1\) for all \(u\in S\) and \(\vert g(C_u)\vert\leq 3\) for all \(u\in V(G')\). Furthermore, \(n_0+i\) is a special element of \(C_{v_i}\) and \(n_0+1\) is an extra special element of \(C_{v_1}=C_{u_y}\).
Now, we shall label the edges in \(F_y\). We may consider \(y\) to be the root of the spanning tree \(F_y\). Now, let \(u\in V(F_y)\setminus \{y\}\) and \(w\) be the unique vertex adjacent to \(u\) on the path from \(u\) to \(y\). Suppose \(w=y\). Since \(y\in V(G')\), there is a special element say \(d_0\) in \(C_y\). Now, change all the labels of the labelled edges according to the following rules: if \(c<d_0\), then \(c\) remains the same; and if \(c\geq d_0\), then \(c\) is changed to \(c+1\). After that label the edge \(yu\) with \(d_0\), i.e., \(E_{yu}=\{d_0\}\). When we change \(d_0\) to \(d_0+1\), the element \(d_0\) was removed from \(C_y\), however, after we labelled the edge \(yu\), \(d_0\) is added back in \(C_y\). Furthermore, \(\vert g(C_y)\vert\) remains the same before and after. Note that if \(b\) was a special element of \(C_u\) for some \(u\in V(G)\) and \(b<d_0\) before the changes, then \(b\) is also a special element of \(C_u\) after the changes. Also, if \(b\) is a special element of \(C_u\) for some \(u\in V(G)\) and \(b\geq d_0\) before the changes, then \(b+1\) is also a special element of \(C_u\) after the changes. Similarly, if \(C_u\) contained an extra special element before the changes, then after the changes, it still contains an extra special element. It is not hard to see that conditions (i) to (v) are satisfied.
Suppose \(w\neq y\). Then, \(w\in S\). Note that \(C_w\) contains a special element, say \(d_1\) (from the labelling of the edges of the part of the Hamiltonian path \(F_x\), from \(u_y\) to \(u_x\)). Now, change all the labels of the labelled edges according to the following rules: if \(c<d_1\), then \(c\) remains the same; and if \(c\geq d_1\), then \(c\) is changed to \(c+1\). After that label the edge \(wu\) with \(d_1\). When we change \(d_1\) to \(d_1+1\), the element \(d_1\) was removed from \(C_w\), however, after we labelled the edge \(wu\), \(d_1\) is added back in \(C_w\). Furthermore, \(\vert g(C_w)\vert\) remains the same before and after. Note that for each \(u\in V(G)\), if \(C_u\) contained an special element before the changes, then after the changes, it still contains an special element. The same is true for extra special element. We remark here that the special element and extra special element in \(C_{u_y}\) could be the same at the beginning. In fact, let’s say \(d_1\) is the special element and extra special element in \(C_{u_y}\). After the changes, \(d_1+1\) becomes the special element in \(C_{u_y}\) whereas \(d_1\) becomes the extra special element. Again, conditions (i) to (v) are satisfied.
Now, we shall label the edges in \(F_z\). Recall that \(F_z\) consists of two trees, one containing \(x\) and one containing \(z\). We may consider \(x\) to be the root of the tree \(T_x\) in \(F_z\) that contains \(x\). Now, let \(u\in V(T_x)\setminus \{x\}\) and \(w\) be the unique vertex adjacent to \(u\) on the path from \(u\) to \(x\). Suppose \(w=x\). There is a special element say \(d_2\) in \(C_x\). Now, change all the labels of the labelled edges according to the following rules: if \(c<d_2\), then \(c\) remains the same; and if \(c\geq d_2\), then \(c\) is changed to \(c+1\). After that label the edge \(xu\) with \(d_2\). When we change \(d_2\) to \(d_2+1\), the element \(d_0\) was removed from \(C_x\), however, after we labelled the edge \(xu\), \(d_2\) is added back in \(C_x\). Furthermore, \(\vert g(C_x)\vert\) remains the same before and after. Note that for each \(u\in V(G)\), if \(C_u\) contained an special element before the changes, then after the changes, it still contains an special element. The same is true for extra special element. It is not hard to see that conditions (i) to (v) are satisfied.
Suppose \(w\neq x\). Then, \(w\in S\). Note that \(C_w\) contains a special element, say \(d_3\) (from the labelling of the edges of the part of the Hamiltonian path \(F_x\), from \(u_y\) to \(u_x\)). Now, change all the labels of the labelled edges according to the following rules: if \(c<d_3\), then \(c\) remains the same; and if \(c\geq d_3\), then \(c\) is changed to \(c+1\). After that label the edge \(wu\) with \(d_3\). As before, we see that conditions (i) to (v) are satisfied.
We do the same for the tree \(T_z\) in \(F_z\) that contains \(z\) except that we do not label the edge \(u_yz\). After we have done all the labelling except for the edges \(xu_y\) and \(zu_y\), conditions (i) to (v) are satisfied. Now, only the edges \(xu_y\) and \(zu_y\) are not labelled. Now, we set \(E_{xz}=E_{xu_y}=E_{zu_y}\).
Note that \(E_{uv}\) is unique for all edges \(uv\) in the interior of \(G_1\) except for edges \(xz,xu_y\) and \(zw\) where \(E_{xz}=E_{xu_y}=E_{zu_y}\). Recall that \(C_{u_y}\) contains a special and an extra special element. Note that if \(u\in S\setminus \{u_y\}\), then \(g(C_u)\) contains at most three consecutive parts: one part arises from the labelling of edges of the Hamiltonian path \(F_x\); one part arises from the labelling of edges of the spanning tree \(F_y\) and one part arises from the labelling of edges of the tree \(T_x\) or \(T_z\). The labelling of edges of \(F_y\) will contribute a single element to \(g(C_u)\). The same is true for labelling of edges of \(T_x\) or \(T_z\). If \(v_iv_{i+1}v_{i+2}\) is the part of the Hamiltonian path with \(v_{i+1}=u\) and \(E_{v_iv_{i+1}}=\{c_1\}\), \(E_{v_{i+1}v_{i+2}}=\{c_2\}\), then \(\{c_1,c_1+1,\dots,c_2\}\subseteq g(C_u)\). If \(u=u_y=v_1\), \(E_{v_1v_2}=\{c_4\}\) and \(c_3\) is the extra special element in \(C_{u_y}\), then \(\{c_3,c_3+1,\dots,c_4\}\subseteq g(C_{u_y})\) (it is possible that \(c_3=c_4\)). The labelling of edges of \(F_y\) will contribute a single element to \(g(C_{u_y})\) and the third element is from the edges \(xu_y\) and \(zu_y\) (since \(E_{xu_y}=E_{zu_y}\)). It is not hard to see that conditions (i) to (v) are satisfied.
Case 2. \(E_{xy}=E_{yz}=E_{xz}\) and \(C_{x}\) contains an extra special element.
Case 2.1. Suppose \(\vert S\vert=1\). This means \(G[S\cup \{x,y,z\}]=K_4\) and \(u_x=u_y=u_z\). Let \(d_0\) be the extra special element in \(C_x\). Now, change all the labels of the labelled edges according to the following rules: if \(c<d_0\), then \(c\) remains the same; and if \(c\geq d_0\), then \(c\) is changed to \(c+1\). After that label the edge \(xu_y\) with \(d_0\), i.e., \(E_{xu_y}=\{d_0\}\). It is not hard to see that conditions (i) to (v) are satisfied.
Since \(y\in V(G')\), there is a special element, say \(d_1\) in \(C_y\). Now, change all the labels of the labelled edges according to the following rules: if \(c<d_1\), then \(c\) remains the same; and if \(c\geq d_1\), then \(c\) is changed to \(c+1\). After that label the edge \(yu_x\) with \(d_1\), i.e., \(E_{yu_x}=\{d_1\}\). Again, conditions (i) to (v) are satisfied.
Since \(z\in V(G')\), there is a special element, say \(d_2\) in \(C_z\). Now, change all the labels of the labelled edges according to the following rules: if \(c<d_2\), then \(c\) remains the same; and if \(c\geq d_2\), then \(c\) is changed to \(c+1\). After that label the edge \(zu_y\) with \(d_2\), i.e., \(E_{zu_y}=\{d_2\}\). Again, conditions (i) to (v) are satisfied.
Case 2.2. Suppose \(\vert S\vert\geq 2\). Let \(d_0\) be the extra special element in \(C_x\). Now, change all the labels of the labelled edges according to the following rules: if \(c<d_0\), then \(c\) remains the same; and if \(c\geq d_0\), then \(c\) is changed to \(c+s\). Now, \(F_x\) is a Hamiltonian path of \(G_1-\{y, z\}\) going from \(x\) to \(u_x\). Recall that \(xu_y\) is an edge in \(F_x\) (Remark 4.7). Therefore, the Hamiltonian path is from \(x\) to \(u_y\) and then from \(u_y\) to \(u_x\). Let the Hamiltonian path in reverse direction from \(u_x=v_1\) to \(x=v_{s+1}\) be \(v_1v_2\dots v_{s+1}\). Note that \(S=\{u_x=v_1,v_2,\dots ,v_s=u_y\}\) and \(s\geq 2\). Now, for \(1\leq i\leq s\), we set \(E_{v_iv_{i+1}}=\{d_0+i-1\}\). Before the changes and the labelling of edges of the Hamiltonian path, \(d_0\) was the initial point of a consecutive part of of \(g(C_x)\). After the changes and labelling of edges of the Hamiltonian path, \(d_0+s-1\) is added to \(g(C_x)\) (from \(E_{xu_y}=\{d_0+s-1\}\)). So, \(\{d_0+s-1,d_0+s,\dots\}\) is a consecutive part of \(g(C_x)\) and \(\vert g(C_x)\vert\) remains the same. However, \(C_x\) has no extra special element anymore. If \(b\neq d_0\) was a special element of \(C_x\) and \(b<d_0\) before the changes, then \(b\) is still a special element of \(C_x\) after the changes. If \(d_0\) was also special in \(C_x\) before the changes, then \(d_0\) was the initial point and also the terminal point of a consecutive part of \(g(C_x)\). So, the consecutive part in \(C_x\) that contained \(d_0\) before the changes was \(\{d_0\}\) a set consists of one element. After the changes and labelling of edges of the Hamiltonian path, \(\{d_0+s-1,d_0+s\}\) is a consecutive part of \(g(C_x)\). Therefore, \(C_x\) still contains a special element, which is \(d_0+s\).
Now, we shall label the edges in \(F_y\). We may consider \(y\) to be the root of the spanning tree \(F_y\). Now, let \(u\in V(F_y)\setminus \{y\}\) and \(w\) be the unique vertex adjacent to \(u\) on the path from \(u\) to \(y\). Suppose \(w=y\). Since \(y\in V(G')\), there is a special element say \(d_1\) in \(C_y\). Now, change all the labels of the labelled edges according to the following rules: if \(c<d_1\), then \(c\) remains the same; and if \(c\geq d_1\), then \(c\) is changed to \(c+1\). After that label the edge \(yu\) with \(d_1\), i.e., \(E_{yu}=\{d_0\}\). It is not hard to see that conditions (i) to (v) are satisfied.
Suppose \(w\neq y\). Then, \(w\in S\). Note that \(C_w\) contains a special element, say \(d_2\) (from the labelling of the edges of the Hamiltonian path \(F_x\) in reverse direction, from \(u_x\) to \(x\)). Now, change all the labels of the labelled edges according to the following rules: if \(c<d_2\), then \(c\) remains the same; and if \(c\geq d_2\), then \(c\) is changed to \(c+1\). After that label the edge \(wu\) with \(d_2\). Again, conditions (i) to (v) are satisfied.
We shall label the edges in \(F_z\) using similar process. Note that \(E_{uv}\) is unique for all edges \(uv\) in the interior of \(G_1\). Furthermore, if \(u\in S\), then \(g(C_u)\) contains at most three consecutive parts: one part arises from the labelling of edges of the Hamiltonian path \(F_x\) in reverse order; one part arises from the labelling of edges of the spanning tree \(F_y\) and one part arises from the labelling of edges of the tree \(T_x\) or \(T_z\). It is not hard to see that conditions (i) to (v) are satisfied.
This completes the proof of the theorem. \(\square\)
The following corollary (which is Theorem 1.1) then follows from Corollary 2.9, Lemma 3.4 and Theorem 4.8.
Corollary 4.9. If \(G\) is planar, then \(i(G)\leq 3\).
By Lemmas 3.2 and 3.7, \(G=\mathfrak F(\{B_u\}_{u\in V(G)})\) for some \(\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\) such that \(L(\{B_u\}_{u\in V(G)})=\{1,2,\dots, m\}\) and each \(i\in \{1,2,\dots, m\}\) is contained in at least two \(B_u\)’s. This motivates us to consider the following two parameters: \[\begin{aligned} m_{\mathcal T_1} (G) &=\min \left\{ \left\vert L(\{B_u\}_{u\in V(G)}) \right\vert\ : \ G=\mathfrak F(\{B_u\}_{u\in V(G)})\ \ \text{for some}\ \ \{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0} \right\};\\ &\\ m_{\mathcal T_2} (G) &=\min \left\{ \left\vert L(\{B_u\}_{u\in V(G)}) \right\vert\ : \ G=\mathfrak F(\{B_u\}_{u\in V(G)})\ \ \text{for some}\ \ \{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0} \right.\\ &\hskip 2cm \left. \vphantom{\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0} } \text{and}\ \ \vert B_u\cap B_v\vert\leq 1\ \ \text{for all}\ \ u,v\in V(G)\ \ \text{with}\ \ u\neq v \right\}. \end{aligned}\]
The two parameters \(m_{\mathcal T_1} (G)\) and \(m_{\mathcal T_2} (G)\) will be called minimum \(\mathcal T_1\)-size number and minimum \(\mathcal T_2\)-size number, respectively. The following lemma is obvious.
Lemma 5.1. \(m_{\mathcal T_1} (G)\leq m_{\mathcal T_2} (G)\).
We note here that in general \(m_{\mathcal T_1} (G)\neq m_{\mathcal T_2} (G)\). In fact, in Example 3.5, it can be seen that \(m_{\mathcal T_1} (G)=2\) and \(m_{\mathcal T_2} (G)=3\).
Lemma 5.2. The following statements are equivalent:
\(G\) is a complete graph.
\(m_{\mathcal T_2} (G)=1\).
\(m_{\mathcal T_1} (G)=1\).
Proof. ((a) \(\Rightarrow\) (b)) Suppose \(G\) is a complete graph. We set \(B_u=\{1\}\) for all \(u\in V(G)\). Then, \(G=\mathfrak F(\{B_u\}_{u\in V(G)})\) and \(\vert B_u\cap B_v\vert=1\) for all \(u,v\in V(G)\) with \(u\neq v\). Hence, \(L(\{B_u\}_{u\in V(G)})=\{1\}\) and \(m_{\mathcal T_2} (G)=1\).
((b) \(\Rightarrow\) (c)) It follows from Lemma 5.1.
((c) \(\Rightarrow\) (a)) Since \(m_{\mathcal T_1} (G)=1\), there is a \(\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\) such that \(G=\mathfrak F(\{B_u\}_{u\in V(G)})\) and \(B_u=B_v\) for all \(u,v\in V(G)\). Therefore, \(G\) is a complete graph. \(\square\)
Lemma 5.3. \(m_{\mathcal T_2} (G)\leq \vert E(G)\vert\).
Proof. Label each of the edges of \(G\) with an element in \(\mathbb N\). All the edges are labelled differently, i.e., \(E_{uv}\neq E_{u'v'}\) for distinct edges \(uv\) and \(u'v'\). By Lemma 4.5, \(\{E_{uv}\}_{u\sim_Gv}\) is \(\mathcal T_2\)-compatible. By part (b) of Lemma 3.8, \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\in\mathcal T_2\) where \(C_u=\bigcup_{v\in N_G(u)} E_{uv}\) for all \(u\in V(G)\). Note that \(L(\{C_u\}_{u\in V(G)})=\bigcup_{u\sim_Gv}E_{uv}\). Hence, \(\vert L(\{C_u\}_{u\in V(G)})\vert=\vert E(G)\vert\) and \(m_{\mathcal T_2} (G)\leq \vert E(G)\vert\). \(\square\)
Lemma 5.4. If \(G\) is not \(K_3\)-free, then \(m_{\mathcal T_2} (G)\leq \vert E(G)\vert-2\).
Proof. If \(G\) is not \(K_3\)-free, then there are three vertices \(x,y,z\) such that \(G[\{x,y,z\}]=K_3\) is a triangle. Label the three edges with 1. Next, label the rest of the edges with different elements in \(\mathbb N\setminus \{1\}\), i.e., \(E_{uv}\neq E_{u'v'}\) for distinct edges \(uv\) and \(u'v'\) in \(E(G)\setminus \{xy,yz,zx\}\). By Lemma 4.5, \(\{E_{uv}\}_{u\sim_Gv}\) is \(\mathcal T_2\)-compatible. By part (b) of Lemma 3.8, \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\in\mathcal T_2\) where \(C_u=\bigcup_{v\in N_G(u)} E_{uv}\) for all \(u\in V(G)\). Note that \(L(\{C_u\}_{u\in V(G)})=\bigcup_{u\sim_Gv}E_{uv}\). So, \(\vert L(\{C_u\}_{u\in V(G)})\vert=\vert E(G)\vert-2\) and \(m_{\mathcal T_2} (G)\leq \vert E(G)\vert-2\). \(\square\)
Theorem 5.5. The following statements are equivalent:
\(G\) is \(K_3\)-free.
\(m_{\mathcal T_1} (G)= \vert E(G)\vert\).
\(m_{\mathcal T_2} (G)= \vert E(G)\vert\).
Proof. ((a) \(\Rightarrow\) (b)) Suppose \(G\) is \(K_3\)-free. By Lemmas 5.1 and 5.3, \(m_{\mathcal T_1} (G)\leq \vert E(G)\vert\). Suppose \(m_{\mathcal T_1} (G)<\vert E(G)\vert\). Then, there exists a \(\{B_u\}_{u\in V(G)}\subseteq 2^{\mathbb N}_{0}\) such that \(G=\mathfrak F(\{B_u\}_{u\in V(G)})\) and \(\left\vert L(\{B_u\}_{u\in V(G)}) \right\vert=m_{\mathcal T_1} (G)\). If \(L(\{B_u\}_{u\in V(G)})\) contains an element \(c\) such that \(c\) is contained only in \(B_{u_0}\) for a particular vertex \(u_0\), then we set \(C_{u_0}=B_{u_0}\setminus \{c\}\) and \(C_u=B_u\) for all \(u\in V(G)\). Note that \(C_u\cap C_v=B_u\cap B_v\) for all \(u,v\in V(G)\) as \(c\notin B_v\) for all other \(v\in V(G)\setminus \{u_0\}\). Therefore, \(G=\mathfrak F(\{C_u\}_{u\in V(G)})\) and \(\left\vert L(\{C_u\}_{u\in V(G)}) \right\vert<\left\vert L(\{B_u\}_{u\in V(G)}) \right\vert=m_{\mathcal T_1} (G)\), a contradiction. Hence, we may assume that each \(c\in L(\{B_u\}_{u\in V(G)})\) is contained in at least two different \(B_u\)’s.
Let \(E_{uv}=B_u\cap B_v\) for all \(u\sim_Gv\). Note that \(\vert E_{uv}\vert\) may be greater than 1. Let \(c\in L(\{B_u\}_{u\in V(G)})\). There are distinct vertices \(u_1\) and \(u_2\) such that \(c\in B_{u_1}\cap B_{u_2}=E_{u_1u_2}\). Thus, \(L(\{B_u\}_{u\in V(G)})\subseteq \bigcup_{u\sim_Gv}E_{uv}\). Clearly, \(\bigcup_{u\sim_Gv}E_{uv}\subseteq L(\{B_u\}_{u\in V(G)})\). Hence, \(L(\{B_u\}_{u\in V(G)})=\bigcup_{u\sim_Gv}E_{uv}\).
Suppose \(E_{u_1v_1}\cap E_{u_2v_2}\neq \varnothing\) for some distinct edges \(u_1v_1\) and \(u_2v_2\). We may assume that \(u_1,v_1\) and \(u_2\) are distinct vertices. Let \(c\in E_{u_1v_1}\cap E_{u_2v_2}\). Then, \(c\in B_{u_1}\cap B_{v_1}\cap B_{u_2}\). So, \(G[\{u_1,v_1,u_2\}]=K_3\), a contradiction. So, we may assume that \(E_{uv}\cap E_{u'v'}= \varnothing\) for distinct edges \(uv\) and \(u'v'\).
Now, \[\begin{aligned} m_{\mathcal T_1} (G)=\left\vert L(\{B_u\}_{u\in V(G)})\right\vert =\left\vert\bigcup_{u\sim_Gv}E_{uv}\right\vert=\sum\limits_{u\sim_Gv} \vert E_{uv}\vert \geq \vert E(G)\vert, \end{aligned}\] a contradiction. Hence, \(m_{\mathcal T_1} (G)=\vert E(G)\vert\).
((b) \(\Rightarrow\) (c)) It follows from Lemmas 5.1 and 5.3.
((c) \(\Rightarrow\) (d)) It follows from Lemma 5.4. \(\square\)
The authors have no relevant financial or non-financial interests to disclose.
Cheng Yeaw Ku is supported by the Singapore Ministry of Education AcRF Tier 1 grant RG105/25.