New families of tripartite graphs with local antimagic chromatic number 3

1. Introduction

Let \(G=(V, E)\) be a graph of size \(q\). For integers \(c < d\), let \([c,d] = \{n\in\mathbb{Z}\;|\; c\le n\le d\}\). A bijection \(f: E\to [1,q]\) is called a local antimagic labeling if \(f^{+}(u)\neq f^{+}(v)\) whenever \(uv\in E\), where\(f^{+}(u)=\sum f(e)\) over all the edge(s) \(e\) incident to \(u\). The mapping \(f^{+}\) is called a vertex labeling of \(G\) induced by \(f\), and the labels assigned to vertices are called induced colors under \(f\). The color number of a local antimagic labeling \(f\) is the number of distinct induced colors under \(f\), denoted by \(c(f)\). Moreover, \(f\) is called a local antimagic \(c(f)\)-coloring and \(G\) is local antimagic \(c(f)\)-colorable. The local antimagic chromatic number \(\chi_{la}(G)\) is defined to be the minimum number of colors taken over all colorings of \(G\) induced by local antimagic labelings of \(G\) [1]. Thus \(\chi_{la}(G)\ge \chi(G)\), the chromatic number of \(G\).

Very few results on the local antimagic chromatic number of regular graphs are known (see [1,3]). Throughout this paper, we let \(O_m\) be the null graph of order \(m\) and \(aP_2\) be the 1-regular graph of \(a\ge 1\) component(s) of path \(P_2\). Moreover, let \(V(aP_2\vee O_m) = \{u_i, v_i, x_j\;|\; 1\le i\le a, 1\le j\le m\}\) and \(E(aP_2 \vee O_m) = \{u_ix_j, v_ix_j, u_iv_i\;|\; 1\le i\le a, 1\le j\le m\}\). We also let \(V(a(P_2\vee O_m)) = \{u_i, v_i, x_{i,j}\;|\; 1\le i\le a, 1\le j\le m\}\) and \(E(a(P_2\vee O_m)) = \{u_ix_{i,j}, v_ix_{i,j}, u_iv_i\;|\; 1\le i\le a, 1\le j\le m\}\).

cIn [2], the author proved that all connected graphs without a \(P_2\) component admit a local antimagic labeling. On the other hand, it is clear that \(O_m\) and a graph with a \(P_2\) component cannot have a local antimagic labeling. Thus, \(O_m\), \(m\ge 1\) and \(aP_2\), \(a\ge 1\) are the only families of regular graphs without local antimagic chromatic number. In [1], it was shown that \(\chi_{la}(aP_2\vee O_1) = 3\) for \(a\ge 1\). In the following sections, we extend the ideas in [4,5] to construct various families of tripartite graphs of size \((4n+1)\times (2k+1)\) and \((4n+3)\times (2k+1)\), for \(n, k\ge 1\), respectively, and proceed to prove that all these graphs have local antimagic chromatic number 3. Consequently, we obtained new families of regular tripartite graphs with local antimagic chromatic number 3.

2. Graphs of size \((4n+1)\times (2k+1)\)

For \(k\ge 1\), we now consider the following \((4n+1)\times (2k+1)\) matrix for \(n\ge 2\). Note that when \(n=1\), the required \(5\times (2k+1)\) matrix is given by rows \(f(u_i, x_{i,1})\), \(f(u_i, x_{i,2})\), \(f(u_iv_i)\), \(f(v_ix_{i,1})\) and \(f(v_1x_{i,2})\) of the matrix below. Moreover, the entries in column \(k+1\) appears in both parts of the matrix. In the following matrix, \(2\le j\le n\).

Let us list the range of entries for each row of the above matrix:

where \(K=2k+1\) and \(j\) runs through \(2\) to \(n\). One may see that the entries of the matrix form \([1, (4n+1)(2k+1)]\).

We now have the following observations.

(a) For \(n\ge 2\) and each \(i\in [1,2k+1]\), the sum of the first \(2n+1\) row entries is \(f^+(u_i)= [f(u_ix_{i,1})+f(u_ix_{i,2})+f(u_iv_i)]+\sum\limits_{j=1}^n(f(u_ix_{2j-1})+f(u_ix_{2j})= [2n(8k+4)-k+1]+\sum\limits^{n}_{j=2} [2(n-j)(8k+4)+14k+8] = 8kn^2+6kn+4n^2+k+4n+1\). Note that, this formula also holds when \(n=1\).

(b) Similar to (a), for \(n\ge 2\) and each \(i\in [1,2k+1]\), the sum of the last \(2n+1\) row entries is \(f^+(v_i) = 11k+7+\sum\limits^{n}_{j=2} [2j(8k+4)-6k-2] = 8kn^2+2kn+4n^2+k+2n+1\). Note that, this formula also holds when \(n=1\).

(c) For each \(i\in [1,k]\) and \(j\in [1,2n]\), each of \(f(u_ix_{i,j}) + f(v_{2k+2-i}x_{2k+2-i,j})\), \(f(v_ix_{i,j}) + f(u_{2k+2-i}x_{2k+2-i,j})\) and \(f(u_{k+1}x_{k+1,j}) + f(v_{k+1}x_{k+1,j})\) is a constant \(n(8k+4)+4k+3\).

(d) We may write down the expression for each \(f(u_ix_{i,l})\) and \(f(v_ix_{i,l})\) as follows:

\(f(u_ix_{i,1})=\begin{cases} (2n-1)(4k+2)+5k+3+i, & 1\le i\le k;\\ (2n-1)(4k+2) +3k+2 + i, & k+1\le i\le 2k+1. \end{cases}\)

\(f(v_ix_{i,1})=\begin{cases} (4k+2)-k-1+i, & 1\le i\le k+1;\\ (4k+2) -3k-2 + i, & k+2\le i\le 2k+1. \end{cases}\)

\(f(u_ix_{i,2})=\begin{cases} 2n(4k+2)-2k-2i, & 1\le i\le k;\\ 2n(4k+2)+1-2i, & k+1\le i\le 2k+1. \end{cases}\)

\(f(v_ix_{i,2})=\begin{cases} (4k+2)+4k+4-2i, & 1\le i\le k+1;\\ (4k+2)+6k+5-2i, & k+2\le i\le 2k+1. \end{cases}\)

For \(2\le j\le n\), \(f(u_ix_{i,2j-1})=\begin{cases} (2n-2j+1)(4k+2)+5k+3+i, & 1\le i\le k;\\ (2n-2j+1)(4k+2) +3k+2 + i, & k+1\le i\le 2k+1. \end{cases}\)

\(f(v_ix_{i,2j-1})=\begin{cases} (2j-1)(4k+2)-k+1+i, & 1\le i\le k+1;\\ (2j-1)(4k+2) -3k-2 + i, & k+2\le i\le 2k+1. \end{cases}\)

\(f(u_ix_{i,2j})=\begin{cases} (2n-2j)(4k+2)+5k+3-i, & 1\le i\le k;\\ (2n-2j)(4k+2) +7k+4 -i, & k+1\le i\le 2k+1. \end{cases}\)

\(f(v_ix_{i,2j})=\begin{cases} 2j(4k+2)-k+1-i, & 1\le i\le k+1;\\ 2j(4k+2) +k+2 -i, & k+2\le i\le 2k+1. \end{cases}\)

(e) Suppose \(2k+1=(2r+1)(2s+1)\), \(r,s\ge 1\). Note that \(1\le i\le k\) if and only if \(k+2\le 2k+2-i\le 2k+1\). For \(1\le i\le k\), we may see from Observation (d) that \[\begin{aligned} f&(u_ix_{i,2j-1})+f(v_{2k+2-i},x_{2k+2-i,2j-1}) \\ &=[(2n-2j+1)(4k+2)+5k+3+i]+[(2j-1)(4k+2) -3k-2 + (2k+2-i)]\\&= 2n(4k+2)+4k+3=n(8k+4)+4k+3. \end{aligned}\] Similarly, we may obtain that \(f(u_ix_{i,l})+f(v_{2k+2-i},x_{2k+2-i,l})=n(8k+4)+4k+3\) for each \(l\in [1, 2n]\).

Thus, for each \(a \in [1,r]\) and \(j\in [1,2n]\), each of \[\sum^{2s+1}_{b=1} [f(u_{(a-1)(2s+1)+b}x_{(a-1)(2s+1)+b,j}) + f(v_{2k+2-(a-1)(2s+1)-b}x_{2k+2-(a-1)(2s+1)-b,j})],\tag{1}\] \[\sum^{2s+1}_{b=1} [f(v_{(a-1)(2s+1)+b}x_{(a-1)(2s+1)+b,j}) + f(u_{2k+2-(a-1)(2s+1)-b}x_{2k+2-(a-1)(2s+1)-b,j})],\tag{2}\] \[\sum^{2s+1}_{b=1} [f(u_{r(2s+1)+b}x_{r(2s+1)+b,j}) + f(v_{2k+2-r(2s+1)-b}x_{2k+2-r(2s+1)-b,j})],\label{eq-d3} \tag{3}\] is a constant \((2s+1)[n(8k+4)+4k+3]\).

Consider \(G = (2k+1)(P_2 \vee O_{2n})\). By Observations (a) and (b) above, we can now define a bijection \(f : E(G) \to [1, (4n+1)(2k+1)]\) according to the table above. Clearly, for \(1\le i\le 2k+1\), \(f^+(u_i) > f^+(v_i)\).

Now, for each \(i\in [1,k]\) and \(j\in [1,2n]\), first delete the edges \(v_ix_{i,j}\) and \(v_{2k+2-i}x_{2k+2-i,j}\), and then add the edges \(v_{2k+2-i}x_{i,j}\) and \(v_ix_{2k+2-i,j}\) with labels \(f(v_{2k+2-i}x_{2k+2-i,j})\) and \(f(v_ix_{i,j})\), respectively. Finally, we rename \(x_{i,j}\) by \(y_{i,j}\) and \(x_{2k+2-i,j}\) by \(z_{i,j}\). We still denote this new labeling by \(f\). By Observation (c), \(f^+(y_{i,j})=f^+(z_{i,j})=n(8k+4)+4k+3\). It is easy to verify that \(f^+(u_i)\), \(f^+(v_i)\) and \(f^+(y_{i,j})\) are distinct for all possible \(n, k\). We denote the resulting graph by \(G_{2n}(k+1)\). Note that \(G_{2n}(k+1)\) has \(k+1\) components.

Example 2.2. Consider \(n = 2\) and \(k=4\). We have the following table.

\(i \)	1	2	3	4	5	6	7	8	9
\(f(u_ix_i,1)\)	78	79	80	81	73	74	75	76	77
\(f(u_ix_i,2)\)	62	60	58	56	63	61	59	57	55
\(f(u_ix_i,3)\)	42	43	44	45	37	38	39	40	41
\(f(u_ix_i,4)\)	22	21	20	19	27	26	25	24	23
\(f(u_iv_i) \)	1	2	3	4	5	6	7	8	9
\(f(v_ix_i,1)\)	14	15	16	17	18	10	11	12	13
\(f(v_ix_i,2)\)	36	34	32	30	28	35	33	31	29
\(f(v_ix_i,3)\)	50	51	52	53	54	46	47	48	49
\(f(v_ix_i,4)\)	68	67	66	65	64	72	71	70	69

By the construction above Theorem 2.1, we have the graph \(G_4(5)\) as shown in Figure 1.

We may make use of Observation (e) to construct a new graph with local antimagic chromatic number 3 from \(G_{2n}(k+1)\). Let us show an example first. Suppose \(2k+1= (2r+1)(2s+1)\), \(r, s\ge 1\).

Example 2.3. Consider \(n = 2\), \(k=4\) again. Now we have \(r=s=1\). Consider the graph \(G=G_{2n}(k+1)\). Now \(V(G)=\{u_i, v_i\;|\; 1\le i\le 9\}\cup\{y_{i,j}, z_{i,j}\;|\; 1\le i\le 4, 1\le j\le 4\}\). From Observation (d) we have \[\begin{aligned} f^+(y_{1,j})+f^+(y_{2,j})+f^+(y_{3,j}) &=[f(u_1x_{1,j})+f(v_9x_{9,j})]+[f(u_2x_{2,j})+f(v_8x_{8,j})]\\& \quad +[f(u_3x_{3,j})+f(v_7x_{7,j})]=273,\\ f^+(z_{1,j})+f^+(z_{2,j})+f^+(z_{3,j}) & =[f(v_1x_{1,j})+f(u_9x_{9,j})]+[f(v_2x_{2,j})+f(u_8x_{8,j})]\\& \quad+[f(v_3x_{3,j})+f(u_7x_{7,j})]=273,\\ f^+(y_{4,j})+f^+(x_{5,j})+f^+(z_{4,j}) &=[f(u_4x_{1,j})+f(v_6x_{2,j})]+[f(u_5x_{5,j})+f(v_5x_{5,j})]\\& \quad+[f(u_6x_{6,j})+f(v_4x_{4,j})]=273. \end{aligned}\]

For each \(j\in[1,4]\), we (i) merge the vertices \(y_{1,j}, y_{2,j}, y_{3,j}\) as a new vertex (still denote by \(y_{1,j}\)) of degree 6; (ii) merge the vertices \(z_{1,j}, z_{2,j}, z_{3,j}\) as a new vertex (still denote by \(z_{1,j}\)) of degree 6; and (iii) merge \(y_{4,j}, x_{5,j}, z_{4,j}\) (denote by \(x_{5,j}\)) of degree 6.

Suppose \(2k+1 = (2r+1)(2s+1)\), \(r,s\ge 1\). Consider the graph \(G_{2n}(k+1)\). For each \(a\in[1,r]\) and \(j\in[1,2n]\), we can merge all \(2s+1\) vertices in \(\{y_{(a-1)(2s+1)+b, j}\;|\;b\in[1, 2s+1]\}\), \(\{z_{(a-1)(2s+1)+b, j}\;|\;b\in[1, 2s+1]\}\), and \(\{x_{r(2s+1)+b, j}\;|\;b\in[1, 2s+1]\}\). The new vertices are denoted by \(y_{(a-1)(2s+1)+1,j}\), \(z_{(a-1)(2s+1)+1,j}\) and \(x_{k+1,j}\), respectively. By Eqs.(1), (2) and (3), we have \(f^+(y_{(a-1)(2s+1)+1,j})=f^+(z_{(a-1)(2s+1)+1,j})=f^+(x_{k+1,j})=(2s+1)[n(8k+4)+4k+3]\). Let the graph just obtained be \(G_{2n}(2r+1,2s+1)\). Note that \(G_{2n}(2r+1,2s+1)\) has \(r+1\) components.

3. Graphs of size \((4n+3)\times (2k+1)\)

In what follows, we refer to the following \((4n+3)\times (2k+1)\) matrix to obtain results similar to Theorems 2.1 and 2.4. For \(1\le j\le n\), we have

Let us list the range of entries for each row of the above matrix:

\(\begin{array}{|l|*{3}{c|}} {\rm Row} & f(u_ix_{i,2j-1}) & f(u_ix_{i,2j}) & f(u_ix_{i,2n+1}) \\\hline {\rm Range} & [1+(4n-2j+4)K, (4n-2j+5)K] & [1+(4n-2j+3)K, (4n-2j+4)K] & [1+(2n+2)K, (2n+3)K] \end{array}\)

\(\begin{array}{|l|*{4}{c|}} {\rm Row} & f(u_iv_i) & f(v_ix_{i,1}) & f(v_ix_{i,2j}) & f(v_ix_{i,2j+1})\\\hline {\rm Range} & [1, K] & [1+K, 2K] & [1+2jK, (2j+1)K] & [1+(2j+1)K, (2j+2)K] \end{array}\) ,
where \(K=2k+1\) and \(j\) runs through \(1\) to \(n\). One may see that the entries of the matrix form \([1, (4n+3)(2k+1)]\).

By a similar argument for Observations (a) to (e) in Section 2, we have the following observations.

(1) For each column, the sum of the first \(2n+2\) entries is \(f^+(u_i) = (n+1)(3n+1)(4k+2) + n + 2k+2\).

(2) For each column, the sum of the last \(2n+2\) entries is \(f^+(v_i) = (n+1)^2(4k+2)+n+1\).

(3) For each \(i\in[1,k]\) and \(j\in[1,2n+1]\), each of \(f(u_ix_{i,j}) + f(v_{2k+2-i}x_{2k+2-i,j})\), \(f(v_ix_{i,j}) + f(u_{2k+2-i}x_{2k+2-i,j})\), and \(f(u_{k+1}x_{k+1,j}) + f(v_{k+1}x_{k+1,j})\) is a constant \((2n+2)(4k+2)+1\).

(4) Suppose \(2k+1=(2r+1)(2s+1)\), \(r,s\ge 1\). For each \(a\in[1,r]\) and \(j\in[1,2n+1]\), each of \[\sum^{2s+1}_{b=1} [f(u_{(a-1)(2s+1)+b}x_{(a-1)(2s+1)+b,j}) + f(v_{2k+2-(a-1)(2s+1)-b}x_{2k+2-(a-1)(2s+1)-b,j})],\tag{4}\] \[\sum^{2s+1}_{b=1} [f(v_{(a-1)(2s+1)+b}x_{(a-1)(2s+1)+b,j}) + f(u_{2k+2-(a-1)(2s+1)-b}x_{2k+2-(a-1)(2s+1)-b,j})],\tag{5}\] \[\sum^{2s+1}_{b=1} [f(u_{r(2s+1)+b}x_{r(2s+1)+b,j}) + f(v_{2k+2-r(2s+1)-b}x_{2k+2-r(2s+1)-b,j})],\tag{6}\] is a constant \((2s+1)[ (2n+2)(4k+2)+1]\).

Similar to graph \(G_{2n}(k+1)\) in Theorem 2.1, we also define \(G_{2n+1}(k+1)\) of \(k+1\) components similarly such that the \(i\)-th component has vertex set \(\{u_i, v_i, u_{2k+2-i}, v_{2k+2-i}, y_{i,j}, z_{i,j} \mid 1\le j\le 2n+1\}\) and edge set \(\{u_iv_i, u_{2k+2-i}v_{2k+2-i}, u_iy_{i,j}, v_{2k+2-i}y_{i,j}, v_iz_{i,j}, u_{2k+2-i}z_{i,j}\mid 1\le j\le 2n+1\}\) for \(1\le i\le k\), and the \((k+1)\)-st component is the \(P_2\vee O_{2n+1}\) with vertex set \(\{u_{k+1}, v_{k+1}, x_{k+1,j} \mid 1\le j\le 2n+1\}\) and edge set \(\{u_{k+1}v_{k+1}, u_{k+1}x_{k+1,j}, v_{k+1}x_{k+1,j}\mid 1\le j\le 2n+1\}\). Moreover, by Observation (3), \(f^+(y_{i,j}) = f^+(z_{i,j}) = (2n+2)(4k+2)+1\). It is easy to verify that \(f^+(u_i), f^+(v_i)\) and \(f^+(y_{i,j})\) are distinct for all possible \(n,k\).

For \(2k+1 = (2r+1)(2s+1), r,s\ge 1\), by Observation (4) above, we also define \(G_{2n+1}(2r+1,2s+1)\) as in Theorem 2.4 with \(r+1\) components and similar vertex set with vertices \(y_{(a-1)(2s+1)+1,j}\), \(z_{(a-1)(2s+1)+1,j}\) and \(x_{k+1,j}\) for \(1\le a\le 2r+1\), \(1\le j\le 2n+1\). By Eqs. (4), (5) and (6), we have \(f^+(y_{(a-1)(2s+1)+1,j})=f^+(z_{(a-1)(2s+1)+1,j})=f^+(x_{k+1,j})=(2s+1)[(2n+2)(4k+2)+1]\).

Example 3.3. Take \(n=2\), \(k=4\), we have the following table and graph \(G_5(5)\) (Figure 3) with the defined labeling.

\(i\)	1	2	3	4	5	6	7	8	9
\(f(u_ix_i,1)\)	99	98	97	96	95	94	93	92	91
\(f(u_ix_i,2)\)	82	83	84	85	86	87	88	89	90
\(f(u_ix_i,3)\)	81	80	79	78	77	76	75	74	73
\(f(u_ix_i,4)\)	64	65	66	67	68	69	70	71	72
\(f(u_ix_i,5)\)	63	62	61	60	59	58	57	56	55
\(f(u_iv_i)\)	1	2	3	4	5	6	7	8	9
\(f(v_ix_i,1)\)	18	17	16	15	14	13	12	11	10
\(f(v_ix_i,2)\)	19	20	21	22	23	24	25	26	27
\(f(v_ix_i,3)\)	36	35	34	33	32	31	30	29	28
\(f(v_ix_i,4)\)	37	38	39	40	41	42	43	44	45
\(f(v_ix_i,5)\)	54	53	52	51	50	49	48	47	46

If we take \(r=s=1\), we can get \(G_5(3,3)\) which is a 6-regular graph (Figure 4).

Note that we may also apply the delete-add process that gives us Theorem 2.6 in [4] to the graphs \(G_{2n}(2r+1,2s+1)\) and \(G_{2n+1}(2r+1,2s+1)\) to obtain two new families of (possibly connected or regular) tripartite graphs with local antimagic chromatic number 3. Denote the respective families of graph as \(\mathcal R_{2n}(2r+1,2s+1)\) and \(\mathcal R_{2n+1}(2r+1,2s+1)\). For example, from graph \(G_4(3,3)\), we may remove the edges \(v_9y_{1,1}\), \(u_1y_{1,1}\) with labels \(13,78\) and \(u_4x_{5,1}, u_6x_{5,1}\) with labels \(81,10\) respectively; and add the edges \(v_9x_{5,1}\) with label 13, \(u_1x_{5,1}\) with label 78, \(u_4y_{1,1}\) with label 81, and \(u_6y_{1,1}\) with label 10. The new graph is in \(\mathcal R_4(3,3)\) and is connected. If we apply this process to \(G_5(3,3)\) involving the edges with labels \(99,10\) and \(96,13\) respectively, we get a connected 6-regular graph in \(\mathcal R_5(3,3)\). Thus, we have the following corollary with the proof omitted.

4. Conclusions and Discussion

In this paper, we constructed several families of infinitely many tripartite graphs of size \((4n+1)\times (2k+1)\) and \((4n+3)\times (2k+1)\) respectively. We then use matrices to show that these graphs have local antimagic chromatic number 3. As a natural extension, we shall in another paper show that such families of graphs of size \((4n+1)\times 2k\) and \((4n+3)\times 2k\) respectively are bipartite but they also have local antimagic chromatic number 3. Interested readers may refer to [6] for more related results.