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)\ne 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 $a{P}_2$ be the 1-regular graph of $a\ge 1$ component(s) of path $P_2$. Moreover, let $V(a{P}_2\vee O_m)=\{u_i,v_i,x_j|1\le i\le a,1\le j\le m\}$ and $E(a{P}_2\vee O_m)=\{u_i{x}_j,v_i{x}_j,u_i{v}_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_i{x}_{i,j},v_i{x}_{i,j},u_i{v}_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 $a{P}_2$, $a\ge 1$ are the only families of regular graphs without local antimagic chromatic number. In [1], it was shown that ${\chi }_{la}(a{P}_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_i{v}_i)$, $f(v_i{x}_{i,1})$ and $f(v_1{x}_{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_i{x}_{i,1})+f(u_i{x}_{i,2})+f(u_i{v}_i)]+\sum _{j=1}^n(f(u_i{x}_{2j-1})+f(u_i{x}_{2j})=[2n(8k+4)-k+1]+\sum _{j=2}^n[2(n-j)(8k+4)+14k+8]=8k{n}^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 _{j=2}^n[2j(8k+4)-6k-2]=8k{n}^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_i{x}_{i,j})+f(v_{2k+2-i}{x}_{2k+2-i,j})$, $f(v_i{x}_{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_i{x}_{i,l})$ and $f(v_i{x}_{i,l})$ as follows:

$f(u_i{x}_{i,1})=\{\begin{array}{ll}(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{array}$

$f(v_i{x}_{i,1})=\{\begin{array}{ll}(4k+2)-k-1+i,& 1\le i\le k+1;\\ (4k+2)-3k-2+i,& k+2\le i\le 2k+1.\end{array}$

$f(u_i{x}_{i,2})=\{\begin{array}{ll}2n(4k+2)-2k-2i,& 1\le i\le k;\\ 2n(4k+2)+1-2i,& k+1\le i\le 2k+1.\end{array}$

$f(v_i{x}_{i,2})=\{\begin{array}{ll}(4k+2)+4k+4-2i,& 1\le i\le k+1;\\ (4k+2)+6k+5-2i,& k+2\le i\le 2k+1.\end{array}$

For $2\le j\le n$, $f(u_i{x}_{i,2j-1})=\{\begin{array}{ll}(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{array}$

$f(v_i{x}_{i,2j-1})=\{\begin{array}{ll}(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{array}$

$f(u_i{x}_{i,2j})=\{\begin{array}{ll}(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{array}$

$f(v_i{x}_{i,2j})=\{\begin{array}{ll}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{array}$

(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{array}{rl}f& (u_i{x}_{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{array}$$ Similarly, we may obtain that $f(u_i{x}_{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 $$\begin{array}{}\text{(1)}& \sum _{b=1}^{2s+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})],\end{array}$$ $$\begin{array}{}\text{(2)}& \sum _{b=1}^{2s+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})],\end{array}$$ $$\begin{array}{}\text{(3)}& \sum _{b=1}^{2s+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})],\end{array}$$ 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_i{x}_{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_i{x}_{2k+2-i,j}$ with labels $f(v_{2k+2-i}{x}_{2k+2-i,j})$ and $f(v_i{x}_{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_i{x}_i,1)$	78	79	80	81	73	74	75	76	77
$f(u_i{x}_i,2)$	62	60	58	56	63	61	59	57	55
$f(u_i{x}_i,3)$	42	43	44	45	37	38	39	40	41
$f(u_i{x}_i,4)$	22	21	20	19	27	26	25	24	23
$f(u_i{v}_i)$	1	2	3	4	5	6	7	8	9
$f(v_i{x}_i,1)$	14	15	16	17	18	10	11	12	13
$f(v_i{x}_i,2)$	36	34	32	30	28	35	33	31	29
$f(v_i{x}_i,3)$	50	51	52	53	54	46	47	48	49
$f(v_i{x}_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{array}{rl}{f}^{+}(y_{1,j})+f^{+}(y_{2,j})+f^{+}(y_{3,j})& =[f(u_1{x}_{1,j})+f(v_9{x}_{9,j})]+[f(u_2{x}_{2,j})+f(v_8{x}_{8,j})]\\ & +[f(u_3{x}_{3,j})+f(v_7{x}_{7,j})]=273,\\ f^{+}(z_{1,j})+f^{+}(z_{2,j})+f^{+}(z_{3,j})& =[f(v_1{x}_{1,j})+f(u_9{x}_{9,j})]+[f(v_2{x}_{2,j})+f(u_8{x}_{8,j})]\\ & +[f(v_3{x}_{3,j})+f(u_7{x}_{7,j})]=273,\\ f^{+}(y_{4,j})+f^{+}(x_{5,j})+f^{+}(z_{4,j})& =[f(u_4{x}_{1,j})+f(v_6{x}_{2,j})]+[f(u_5{x}_{5,j})+f(v_5{x}_{5,j})]\\ & +[f(u_6{x}_{6,j})+f(v_4{x}_{4,j})]=273.\end{array}$$

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:

$\overline{)\begin{array}{lccc}\mathrm{R}\mathrm{o}\mathrm{w}& f(u_i{x}_{i,2j-1})& f(u_i{x}_{i,2j})& f(u_i{x}_{i,2n+1})\\ \mathrm{R}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}& [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}}$

$\overline{)\begin{array}{lcccc}\mathrm{R}\mathrm{o}\mathrm{w}& f(u_i{v}_i)& f(v_i{x}_{i,1})& f(v_i{x}_{i,2j})& f(v_i{x}_{i,2j+1})\\ \mathrm{R}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}& [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_i{x}_{i,j})+f(v_{2k+2-i}{x}_{2k+2-i,j})$, $f(v_i{x}_{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 $$\begin{array}{}\text{(4)}& \sum _{b=1}^{2s+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})],\end{array}$$ $$\begin{array}{}\text{(5)}& \sum _{b=1}^{2s+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})],\end{array}$$ $$\begin{array}{}\text{(6)}& \sum _{b=1}^{2s+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})],\end{array}$$ is a constant $(2s+1)[(2n+2)(4k+2)+1]$.