An edge labeling of a graph \(G = (V, E)\) is said to be local antimagic if it is a bijection \(f:E \to\{1,\ldots ,|E|\}\) such that for any pair of adjacent vertices \(x\) and \(y\), \(f^+(x)\not= f^+(y)\), where the induced vertex label \(f^+(x)= \sum f(e)\), with \(e\) ranging over all the edges incident to \(x\). The local antimagic chromatic number of \(G\), denoted by \(\chi_{la}(G)\), is the minimum number of distinct induced vertex labels over all local antimagic labelings of \(G\). In this paper, we study local antimagic labeling of three disjoint cycles with at least two odd cycles, one of which is \(C_3\). We prove that (1) \(\chi_{la}(C_3+C_3+C_3)=5\) and \(\chi_{la}(C_3+C_3+C_{k})=4\) for \(k\geq 4\); (2) \(\chi_{la}(C_3+C_4+C_{2k+1})=4\); (3) \(\chi_{la}(C_3+C_6+C_{4k+1})=3\); (4) \(\chi_{la}(C_3+C_{10}+C_{8k-3})=3\); (5) \(\chi_{la}(C_3+C_5+C_{14})=4\) and \(\chi_{la}(C_3+C_5+C_{4k+2})=3\) for \(k\neq3\); (6) \(\chi_{la}(C_3+C_{4k+1}+C_{4k+5})=3\) and \(\chi_{la}(C_3+C_{4k+1}+C_{4k+6})=3\).
A graph G = (V, E) is said to be local antimagic if it admits a local antimagic edge labeling, i.e., a bijection f : E → {1, . . . , |E|} such that the induced vertex labeling f + : V → Z given by \(f^{+}(u) = f (e)\), with e ranging over all the edges incident to u, has the property P that any two adjacent vertices have distinct induced vertex labels (see [1,2]). Thus, f + is a coloring of G. Clearly, the order of G must be at least 3. The vertex label \(f^{+}(u)\) is called the induced color of u under f (the color of u, for short, if no ambiguity occurs). The number of distinct induced colors under f is denoted by c(f ), and is called the color number of f . The labeling f is called a local antimagic c(f )-coloring of G. The local antimagic chromatic number of G, denoted by \(\chi_{\mathrm{la}} (G)\), is min{c(f ) | f is a local antimagic labeling of G}. Haslegrave [4] proved that every connected graph other than K2 is local antimagic. Hence \(\chi_{\mathrm{la}} (G)\) is well-defined for every connected or disconnected graph G not containing any isolated edge. For graphs G and H , let G + H be the disjoint union of G and H with vertex set V (G) ∪ V (H) and edge set E(G) ∪ E(H). For convenient, mG is the disjoint union of m ≥ 2 copies of G. For any vertex u ∈ V (G), denote the set of edges incident to u by E(u). We shall use the notation \([a, b]\) := {c ∈ Z | a ≤ c ≤ b}. Unless stated otherwise, all graphs considered in this paper are simple, undirected and of order at least 3. In [3], the authors gave lower and upper bounds for the local antimagic chromatic number of disjoint union of cycles.
Theorem 1.1. For m ≥ 1, let G = Cn1 + Cn2 + · · · + Cnm , where ni ≥ 3, 1 ≤ i ≤ m. Then 3 ≤ \(\chi_{\mathrm{la}} (G) \leq m + 2\).
They also proved that if all but except maybe one cycle are even, then the local antimagic chromatic number is 3.
Theorem 1.2. Let G = Cn1 + Cn2 + · · · + Cnm , where ni ≥ 3 for 1 ≤ i ≤ m, and ni is even for 1 ≤ i ≤ m − 1, then \(\chi_{\mathrm{la}} (G) = 3\).
The next natural step is to determine the local antimagic chromatic number of disjoint union of cycles with at least two odd cycles. In this paper, we study local antimagic edge labeling of three disjoint cycles with at least two odd cycles, one of which is C3 .
First, we consider disjoint union of cycles with at least two C3 ‘s.
Theorem 2.1. For m ≥ 1, let G = \(C_{3} + C_{3} + C_{n}\)1 + Cn2 + · · · + Cnm , where ni ≥ 3, 1 ≤ i ≤ m. Then 4 ≤ \(\chi_{\mathrm{la}} (G) \leq m + 4\).
Proof. Suppose \(\chi_{\mathrm{la}} (G) = 3\). Let a, b, c be the induced vertex labels of G. Then both C3 ‘s have edge labels a+b−c 2 , b+c−a 2 , c+a−b 2 , a contradiction. The result follows from Theorem 1.1.
Lemma 2.2. Let G = (V, E) be a k -regular graph. Suppose f is a local antimagic c-coloring of G. Define \(g(e) := |E|+1 – f (e) for all e \in E\). Then g is a local antimagic c-coloring of G.
Proof. Since f is a bijection X from E to X[1, |E|], g is a bijection from E to [1, |E|] as well. For all u ∈ V , \(g (u) = + g(e) = (|E|+1 – f (e)) = k(|E|+1) – \(f^{+}(u)\)\). Thus, for e∈E(u) e∈E(u) all uv ∈ E , \(g^{+}(u)\) ̸= \(g^{+}(v)\). Hence, g is a local antimagic c-coloring of G.
Theorem 2.3. \(\chi_{\mathrm{la}} (C_{3} + C_{3} + C_{3} ) = 5\).
Proof. By Theorem 2.1, 4 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{3} + C_{3} ) \leq 5\). Suppose \(\chi_{\mathrm{la}} (C_{3} + C_{3} + C_{3} ) = 4\). Let f be a local antimagic 4-coloring of \(C_{3} + C_{3} + C_{3}\) with induced vertex labels a, b, c, d. Note that a, b, c, d ∈ \([3, 17]\) and are all distinct. Without loss of generality, assume the induced vertex labels of the three C3 : H1 , H2 , H3 , are {a, b, c}, {a, b, d} and {a, c, d} respectively. Then the edge labels of H1 are 2 , 2 , 2 . The edge labels of H2 are a+b−d a+b−c b+c−a c+a−b 2 , b+d−a 2 , d+a−b 2 . The edge labels of H3 are 2 , 2 , 2 . As a + b ≡ c ≡ d (mod 2), a + c ≡ b ≡ d (mod 2), a + d ≡ b ≡ c a+c−d c+d−a d+a−c (mod 2), we have b ≡ c ≡ d (mod 2). Since b + c ≡ a (mod 2), a ≡ 0 (mod 2). Note that the sum of all the edge labels of H1 , H2 , H3 are a+b+c 2 , a+b+d 2 , a+c+d 2 respectively. Hence, 9 a+b+c a+b+d a+c+d X + + = i 2 2 2 i=1 3a + 2(b + c + d) = 90.
Without loss of generality, assume b < c < d. Since a is even and appears 3 times as an induced vertex label, a = 8, 10, 12. Define \(g(e) := 10 – f (e) for all e \in E\). By Lemma 2.2, g is a local antimagic 4-coloring and \(g^{+}(u) = 20 – f^{+}(u) for all u \in V\). Thus, it suffices to consider a = 8 and a = 10. Also, since b, c, d all appear twice as an induced vertex label, 5 ≤ b < c < d ≤ 15. (1) a = 8, b + c + d = 33. This implies b, c, d are all odd and b ≤ 9. Thus, b = 5, b = 7 or b = 9. (1.1) b = 5, c + d = 28. This implies c = 13 and d = 15. But H1 has an edge label a+b−c 2 = 0 which is impossible. (1.2) b = 7, c + d = 26. This implies c = 11 and d = 15. But H2 has an edge label a+b−d 2 = 0 which is impossible. (1.3) b = 9, c + d = 24. This implies c = 11 and d = 13. But H1 has an edge label a+b−c 2 = 3 and H3 has an edge label a+c−d 2 = 3, a contradiction. (2) a = 10, b + c + d = 30. This implies b, c, d are all even and {b, c, d} ⊂ {6, 8, 12, 14}. But there is no solution. Therefore, \(\chi_{\mathrm{la}} (C_{3} + C_{3} + C_{3} ) = 5\).
Theorem 2.4. For k ≥ 2, \(\chi_{\mathrm{la}} (C_{3} + C_{3} + C_{2k} ) = 4\).
Proof. By Theorem 2.1, 4 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{3} + C_{2k} ) \leq 5\). We construct a local antimagic 4-coloring of \(C_{3} + C_{3} + C_{2k}\) for k ≥ 2. Note that there are 2k + 6 edges. For the first C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = 1\), \(f (e_{2} ) = 2k + 6\), \(f (e_{3} ) = 2k + 5\). The induced vertex labels are 2k + 6, 2k + 7, 4k + 11.
For the second C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = k + 2\), \(f (e_{2} ) = k + 3\), \(f (e_{3} ) = k + 4\). The induced vertex labels are 2k + 5, 2k + 6, 2k + 7. For C2k , let ei be the i-th edge in the clockwise order for i ∈ \([1, 2k]\). Define f by k \(f (e_{2i-1} ) = 2i\), i ∈ 1, 2 k \(f (e_{2i} ) = 2k + 6 – (2i + 1)\), i ∈ 1, 2 k \(f (e_{2k+1}-2i ) = 2i + 1\), i ∈ 1, 2 k \(f (e_{2k+2}-2i ) = 2k + 6 – 2i\), i ∈ 1, . 2 When k is odd, the edge labels are:
2, 4, . . . , k + 1; 2k + 3, 2k + 1, . . . , k + 6; 3, 5, . . . , k; 2k + 4, 2k + 2, . . . , k + 5.
The induced vertex labels are:
+ k−1 \(f (e_{2i-1} \cap e_{2i} ) = 2k + 5\), i ∈ 1, 2 k−1 \(f^{+}(e_{2i} \cap e_{2i+1} ) = 2k + 7\), i ∈ 1, 2 k−1 \(f^{+}(e_{2k+2}-2i \cap e_{2k+1}-2i ) = 2k + 7\), i ∈ 1, 2 k−1 \(f^{+}(e_{2k+1}-2i \cap e_{2k}-2i ) = 2k + 5\), i ∈ 1, 2 \(f^{+}(e_{1} \cap e_{2k} ) = 2 + 2k + 4 = 2k + 6 f^{+}(ek \cap ek+1 ) = k + 1 + k + 5 = 2k + 6\).
When k is even, the edge labels are:
2, 4, . . . , k; 2k + 3, 2k + 1, . . . , k + 5; 3, 5, . . . , k + 1; 2k + 4, 2k + 2, . . . , k + 6.
The induced vertex labels are:
+ k \(f (e_{2i-1} \cap e_{2i} ) = 2k + 5\), i ∈ 1, 2 k \(f^{+}(e_{2i} \cap e_{2i+1} ) = 2k + 7\), i ∈ 1, − 1 2 k \(f^{+}(e_{2k+2}-2i \cap e_{2k+1}-2i ) = 2k + 7\), i ∈ 1, 2 k \(f^{+}(e_{2k+1}-2i \cap e_{2k}-2i ) = 2k + 5\), i ∈ 1, − 1 2 \(f^{+}(e_{1} \cap e_{2k} ) = 2 + 2k + 4 = 2k + 6 f^{+}(ek \cap ek+1 ) = k + 5 + k + 1 = 2k + 6\).
Therefore, f is a local antimagic labeling of \(C_{3} + C_{3} + C_{2k}\) with induced vertex labels 2k + 5, 2k + 6, 2k + 7, 4k + 11.
Theorem 2.5. For k ≥ 1, \(\chi_{\mathrm{la}} (C_{3} + C_{3} + C_{4k+1} ) = 4\).
Proof. By Theorem 2.1, 4 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{3} + C_{4k+1} ) \leq 5\). We construct a local antimagic 4-coloring of \(C_{3} + C_{3} + C_{4k+1}\) for k ≥ 1. Note that there are 4k + 7 edges. For the first C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = 1\), \(f (e_{2} ) = 4k + 6\), \(f (e_{3} ) = 7\). The induced vertex labels are 8, 4k + 7, 4k + 13. For the second C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = 2\), \(f (e_{2} ) = 4k + 7\), \(f (e_{3} ) = 6\). The induced vertex labels are 8, 4k + 9, 4k + 13. For C4k+1 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 4k + 1]\). Define f by \(f (e_{1} ) = 3\), \(f (e_{2i} ) = 4k + 8 – 4i\), i ∈ \([1, k]\), \(f (e_{2i+1} ) = 4i + 5\), i ∈ \([1, k]\), \(f (e_{2k+2} ) = 4\), f (e2(k+i)+1 ) = 4k + 7 − 4i, i ∈ \([1, k – 1]\), f (e2(k+i)+2 ) = 4i + 6, i ∈ \([1, k – 1]\), \(f (e_{4k+1} ) = 5\).
The edge labels are:
3; 4k+4, 4k, . . . , 8; 9, 13, . . . , 4k+5; 4; 4k+3, 4k−1, . . . , 11; 10, 14, . . . , 4k+2; 5.
The induced vertex labels are: \(f^{+}(e_{1} \cap e_{2} ) = 3 + 4k + 4 = 4k + 7\), \(f^{+}(e_{2i} \cap e_{2i+1} ) = 4k + 13\), i ∈ \([1, k]\) , + \(f (e_{2i+1} \cap e_{2i+2} ) = 4k + 9\), i ∈ \([1, k]\) , + \(f (e_{2k+2} \cap e_{2k+3} ) = 4 + 4k + 3 = 4k + 7\), \(f^{+}(e_{2}(k+i)\)+1 ∩ e2(k+i)+2 ) = 4k + 13, i ∈ \([1, k – 1]\) , \(f^{+}(e_{2}(k+i)\)+2 ∩ e2(k+i)+3 ) = 4k + 9, i ∈ \([1, k – 2]\) , + \(f (e_{4k} \cap e_{4k+1} ) = 4k + 2 + 5 = 4k + 7\), \(f^{+}(e_{1} \cap e_{4k+1} ) = 3 + 5 = 8\).
Therefore, f is a local antimagic labeling of \(C_{3} + C_{3} + C_{4k+1}\) with induced vertex labels 8, 4k + 7, 4k + 9, 4k + 13.
Theorem 2.6. For k ≥ 1, \(\chi_{\mathrm{la}} (C_{3} + C_{3} + C_{4k+3} ) = 4\).
Proof. By Theorem 2.1, 4 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{3} + C_{4k+3} ) \leq 5\). We construct a local antimagic 4-coloring of \(C_{3} + C_{3} + C_{4k+3}\) for k ≥ 1. Note that there are 4k + 9 edges. For the first C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = 1\), \(f (e_{2} ) = 4k + 8\), \(f (e_{3} ) = 7\). The induced vertex labels are 8, 4k + 9, 4k + 15. For the second C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = 2\), \(f (e_{2} ) = 4k + 9\), \(f (e_{3} ) = 6\). The induced vertex labels are 8, 4k + 11, 4k + 15. For C4k+3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 4k + 3]\). Define f by, for i ∈ \([1, k]\), \(f (e_{1} ) = 3\), \(f (e_{2i} ) = 4k + 10 – 4i\), \(f (e_{2i+1} ) = 4i + 5\), \(f (e_{2k+2} ) = 4\), f (e2(k+i)+1 ) = 4k + 11 − 4i, f (e2(k+i)+2 ) = 4i + 4, \(f (e_{4k+3} ) = 5\).
The edge labels are: 3; 4k+6, 4k+2, . . . , 10; 9, 13, . . . , 4k+5; 4; 4k+7, 4k+3, . . . , 11; 8, 12, . . . , 4k+4; 5.
The induced vertex labels are: \(f^{+}(e_{1} \cap e_{2} ) = 3 + 4k + 6 = 4k + 9\), \(f^{+}(e_{2i} \cap e_{2i+1} ) = 4k + 15\), i ∈ \([1, k]\) , + \(f (e_{2i+1} \cap e_{2i+2} ) = 4k + 11\), i ∈ \([1, k – 1]\) , + \(f (e_{2k+1} \cap e_{2k+2} ) = 4k + 5 + 4 = 4k + 9\), \(f^{+}(e_{2}(k+i)\) ∩ e2(k+i)+1 ) = 4k + 11, i ∈ \([1, k]\) , \(f^{+}(e_{2}(k+i)\)+1 ∩ e2(k+i)+2 ) = 4k + 15, i ∈ \([1, k]\) , + \(f (e_{4k+2} \cap e_{4k+3} ) = 4k + 4 + 5 = 4k + 9\), \(f^{+}(e_{1} \cap e_{4k+3} ) = 3 + 5 = 8\).
Therefore, f is a local antimagic labeling of \(C_{3} + C_{3} + C_{4k+3}\) with induced vertex labels 8, 4k + 9, 4k + 11, 4k + 15.
Combining all the above results, we have
Theorem 2.7. \(\chi_{\mathrm{la}} (C_{3} + C_{3} + C_{3} ) = 5\). For k ≥ 4, \(\chi_{\mathrm{la}} (C_{3} + C_{3} + C_{k} ) = 4\).
By Theorem 1.2, \(\chi_{\mathrm{la}} (C_{3} + C_{4} + C_{2k} ) = 3 for k \geq 2\). Here we prove that \(\chi_{\mathrm{la}} (C_{3} + C_{4} + C_{2k+1} ) = 4 for k \geq 1\). First, we restate the following lemma in \([5, Lemma 1]\) or [6, Lemma 2.1].
Lemma 3.1. Let G be a graph and C be a component of G. Suppose there is a local antimagic labeling of G inducing a 2-vertex coloring of C with colors x and y , where x < y . Let X and Y be the sets of vertices in C colored x and y , respectively. Then C is a bipartite graph with bipartition (X, Y ), |X|> |Y |, and x|X|= y|Y |.
We also need the useful lemma proved in [3].
Lemma 3.2. Let G be a disjoint union of cycles with n vertices. Suppose \(\chi_{\mathrm{la}} (G) = 3\). Then the edge labeled 1 is adjacent to the edge labeled n. Moreover, one vertex label is less than n + 1, one is equal to n + 1, and one is greater than n + 1.
Theorem 3.3. For k ≥ 1, \(\chi_{\mathrm{la}} (C_{3} + C_{4} + C_{2k+1} ) = 4\).
Proof. By Theorem 1.1, 3 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{4} + C_{2k+1} ) \leq 5\). Suppose \(\chi_{\mathrm{la}} (C_{3} + C_{4} + C_{2k+1} ) = 3\). Let f be a local antimagic 3-coloring of G, and a, b, c be the induced vertex labels. For C4 , let ei = vi vi+1 be the i-th edge in the clockwise order for i ∈ \([1, 4]\) where v5 = v1 . By Lemma 3.1, all a, b, c must appear as induced vertex labels in C4 . Without loss of generality, assume \(f^{+}(v_{1} ) = a\), \(f^{+}(v_{2} ) = b\), \(f^{+}(v_{3} ) = c\), \(f^{+}(v_{4} ) = b\). Note that a + c = 2b. Thus, b lies between a and c. By Lemma 3.2, b = 2k+9. Since a, b, c are the induced vertex labels of C3 , the edge labels of C3 are a+b−c2 , b+c−a 2 , c+a−b 2 . However, c+a−b 2 = 2b = 2k+9 2 / Z. ∈ Hence, 4 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{4} + C_{2k+1} ) \leq 5\). We construct a local antimagic 4-coloring of \(C_{3} + C_{4} + C_{2k+1}\) for k ≥ 1. Note that there are 2k + 8 edges. For C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = k + 3\), \(f (e_{2} ) = k + 5\), \(f (e_{3} ) = k + 4\). The induced vertex labels are 2k + 7, 2k + 8, 2k + 9. For C4 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 4]\). Define f by \(f (e_{1} ) = k + 1\), \(f (e_{2} ) = k + 7\), \(f (e_{3} ) = k + 2\), \(f (e_{4} ) = k + 6\). The induced vertex labels are 2k + 7, 2k + 8, 2k + 9. For C2k+1 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 2k + 1]\). Define f by \(f (e_{2i-1} ) = i\), \(f (e_{2i} ) = 2k + 8 – i\), for i ∈ \([1, k]\), and \(f (e_{2k+1} ) = 2k + 8\). The edge labels are:
1, 2, . . . , k; 2k + 7, 2k + 6, . . . , k + 8; 2k + 8.
The induced vertex labels are: \(f^{+}(e_{2i-1} \cap e_{2i} ) = 2k + 8\), i ∈ \([1, k]\) , + \(f (e_{2i} \cap e_{2i+1} ) = 2k + 9\), i ∈ \([1, k – 1]\) , + \(f (e_{2k} \cap e_{2k+1} ) = k + 8 + 2k + 8 = 3k + 16\), \(f^{+}(e_{1} \cap e_{2k+1} ) = 1 + 2k + 8 = 2k + 9\).
Therefore, f is a local antimagic labeling of \(C_{3} + C_{4} + C_{2k+1}\) with induced vertex labels 2k + 7, 2k + 8, 2k + 9, 3k + 16.
Theorem 4.1. For k ≥ 1, \(\chi_{\mathrm{la}} (C_{3} + C_{6} + C_{4k+1} ) = 3\).
Proof. By Theorem 1.1, 3 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{6} + C_{4k+1} ) \leq 5\). We construct a local antimagic 3-coloring of \(C_{3} + C_{6} + C_{4k+1}\) for k ≥ 1. Note that there are 4k + 10 edges. For C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = k + 2\), \(f (e_{2} ) = 3k + 9\), \(f (e_{3} ) = 2k + 5\). The induced vertex labels are 3k + 7, 4k + 11, 5k + 14. For C6 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 6]\). Define f by \(f (e_{1} ) = k +1\), \(f (e_{2} ) = 3k +10\), \(f (e_{3} ) = 2k +4\), \(f (e_{4} ) = k +3\), \(f (e_{5} ) = 3k +8\), \(f (e_{6} ) = 2k +6\). The induced vertex labels are 3k + 7, 4k + 11, 5k + 14. For C4k+1 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 4k + 1]\). Define f by, for i ∈ \([1, k]\), \(f (e_{4i-3} ) = k + 1 – i\), \(f (e_{4i-2} ) = 3k + 10 + i\), \(f (e_{4i-1} ) = 2k + 4 – i\), \(f (e_{4i} ) = 2k + 7 + i\), \(f (e_{4k+1} ) = 2k + 7\).
The edge labels are: k, k − 1, . . . , 1; 3k + 11, 3k + 12, . . . , 4k + 10; 2k + 3, 2k + 2, . . . , k + 4; 2k + 8, 2k + 9, . . . , 3k + 7; 2k + 7.
The induced vertex labels are: \(f^{+}(e_{4i-3} \cap e_{4i-2} ) = 4k + 11\), i ∈ \([1, k]\) , \(f^{+}(e_{4i-2} \cap e_{4i-1} ) = 5k + 14\), i ∈ \([1, k]\) , + \(f (e_{4i-1} \cap e_{4i} ) = 4k + 11\), i ∈ \([1, k]\) , + \(f (e_{4i} \cap e_{4i+1} ) = 3k + 7\), i ∈ \([1, k – 1]\) , \(f^{+}(e_{4k} \cap e_{4k+1} ) = 3k + 7 + 2k + 7 = 5k + 14\).
Therefore, f is a local antimagic labeling of \(C_{3} + C_{6} + C_{4k+1}\) with induced vertex labels 3k + 7, 4k + 11, 5k + 14.
Theorem 5.1. For k ≥ 1, \(\chi_{\mathrm{la}} (C_{3} + C_{10} + C_{8k-3} ) = 3\).
Proof. By Theorem 1.1, 3 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{10} + C_{8k-3} ) \leq 5\). We construct a local antimagic 3-coloring of \(C_{3} + C_{10} + C_{8k-3}\) for k ≥ 1. Note that there are 8k + 10 edges. For C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = 4k +3\), \(f (e_{2} ) = 4k +8\), \(f (e_{3} ) = 4k +5\). The induced vertex labels are 8k +8, 8k +11, 8k +13.
For C10 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 10]\). Define f by \(f (e_{1} ) = 1\), \(f (e_{2} ) = 8k + 10\), \(f (e_{3} ) = 3\), \(f (e_{4} ) = 8k + 8\), \(f (e_{5} ) = 5\), \(f (e_{6} ) = 8k + 6\), \(f (e_{7} ) = 2\), \(f (e_{8} ) = 8k + 9\), \(f (e_{9} ) = 4\), \(f (e_{10} ) = 8k + 7\). The edge labels are 1, 2, 3, 4, 5; 8k + 6, 8k + 7, 8k + 8, 8k + 9, 8k + 10. The induced vertex labels are 8k + 8, 8k + 11, 8k + 13. For C8k−3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 8k – 3]\). Define f by \(f (e_{1} ) = 6\). For k odd, \(f (e_{4k-2} ) = 4k + 9\), \(f (e_{4k-1} ) = 4k + 4\), \(f (e_{4k} ) = 4k + 7\), \(f (e_{4k+1} ) = 4k + 6\). For k even, \(f (e_{4k-2} ) = 4k + 6\), \(f (e_{4k-1} ) = 4k + 7\), \(f (e_{4k} ) = 4k + 4\), \(f (e_{4k+1} ) = 4k + 9\). For i ∈ \([0, k – 2]\), 8k + 5 − 4i, i even (≡ 5 mod 8), ( \(f (e_{4i+2} ) = 8k + 2 – 4i\), i odd (≡ 6 mod 8), 8 + 4i, i even (≡ 0 mod 8), ( \(f (e_{4i+3} ) = 9 + 4i\), i odd (≡ 5 mod 8), 8k + 3 − 4i, i even (≡ 3 mod 8), ( \(f (e_{4i+4} ) = 8k + 4 – 4i\), i odd (≡ 0 mod 8), 10 + 4i, i even (≡ 2 mod 8), ( \(f (e_{4i+5} ) = 7 + 4i\), i odd (≡ 3 mod 8), 8k + 2 − 4i, i even (≡ 2 mod 8), ( \(f (e_{8k-3}-4i ) = 8k + 5 – 4i\), i odd (≡ 1 mod 8), 9 + 4i, i even (≡ 1 mod 8), ( \(f (e_{8k-4}-4i ) = 8 + 4i\), i odd (≡ 4 mod 8), 8k + 4 − 4i, i even (≡ 4 mod 8), ( \(f (e_{8k-5}-4i ) = 8k + 3 – 4i\), i odd (≡ 7 mod 8), 7 + 4i, i even (≡ 7 mod 8), ( \(f (e_{8k-6}-4i ) = 10 + 4i\), i odd (≡ 6 mod 8).
Note that (1) 7 + 4i ≥ 7 and 8k + 5 − 4i ≤ 8k + 5. (2) 10 + 4i ≤ 10 + 4(k − 2) = 4k + 2 and 8k + 2 − 4i ≥ 8k + 2 − 4(k − 2) = 4k + 10. (3) By considering mod 8, if two edge labels are equal, then either 8k + a − 4i = a + 4 + 4i′ =⇒ i + i′ = 2k − 1 or 8k + b − 4i = b + 8 + 4i′ =⇒ i + i′ = 2k − 2. Both are impossible. Thus all edge labels are distinct. (4) \(f^{+}(e_{1} \cap e_{2} ) = 6 + 8k + 5 = 8k + 11 and f^{+}(e_{1} \cap e_{8k-3} ) = 6 + 8k + 2 = 8k + 8\). (5) For i ∈ \([0, k – 2]\), 8k + 13, i even, ( + \(f (e_{4i+2} \cap e_{4i+3} ) = 8k + 11\), i odd, 8k + 11, i even, ( \(f^{+}(e_{4i+3} \cap e_{4i+4} ) = 8k + 13\), i odd, 8k + 13, i even, ( \(f^{+}(e_{4i+4} \cap e_{4i+5} ) = 8k + 11\), i odd, 8k + 11, i even, ( \(f^{+}(e_{8k+2}-4i \cap e_{8k+1}-4i ) = 8k + 13\), i odd, 8k + 13, i even, ( \(f^{+}(e_{8k+1}-4i \cap e_{8k}-4i ) = 8k + 11\), i odd, 8k + 11, i even, ( \(f^{+}(e_{8k}-4i \cap e_{8k-1}-4i ) = 8k + 13\), i odd.
For i ∈ \([0, k – 3]\), 8k + 8, i even, ( \(f^{+}(e_{4i+5} \cap e_{4i+6} ) = 8k + 8\), i odd. 8k + 8, i even, ( \(f^{+}(e_{8k-1}-4i \cap e_{8k-2}-4i ) = 8k + 8\), i odd.
(6) When k is even, \(f^{+}(e_{4k-3} \cap e_{4k-2} ) = 10 + 4(k – 2) + 4k + 6 = 8k + 8\), \(f^{+}(e_{4k-2} \cap e_{4k-1} ) = 8k + 13\), \(f^{+}(e_{4k-1} \cap e_{4k} ) = 8k + 11\), \(f^{+}(e_{4k} \cap e_{4k+1} ) = 8k + 13\), and \(f^{+}(e_{4k+1} \cap e_{4k+2} ) = 4k + 9 + 7 + 4(k – 2) = 8k + 8\). When k is odd, \(f^{+}(e_{4k-3} \cap e_{4k-2} ) = 7 + 4(k – 2) + 4k + 9 = 8k + 8\), \(f^{+}(e_{4k-2} \cap e_{4k-1} ) = 8k + 13\), \(f^{+}(e_{4k-1} \cap e_{4k} ) = 8k + 11\), \(f^{+}(e_{4k} \cap e_{4k+1} ) = 8k + 13\), and \(f^{+}(e_{4k+1} \cap e_{4k+2} ) = 4k + 6 + 10 + 4(k – 2) = 8k + 8\). Therefore, f is a local antimagic labeling of \(C_{3} + C_{10} + C_{8k-3}\) with induced vertex labels 8k + 8, 8k + 11, 8k + 13.
Theorem 6.1. For a ≥ 3, 3 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{5} + C_{a} ) \leq 4\).
Proof. By Theorem 1.1, 3 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{5} + C_{a} ) \leq 5\). First, we construct a local antimagic 4-coloring of \(C_{3} + C_{5} + C_{2k+1}\) for k ≥ 1. Note that there are 2k + 9 edges. For C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = 2\), \(f (e_{2} ) = k + 6\), \(f (e_{3} ) = k + 8\). The induced vertex labels are k + 8, k + 10, 2k + 14. For C5 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 5]\). Define f by \(f (e_{1} ) = 1\), \(f (e_{2} ) = k + 7\), \(f (e_{3} ) = 3\), \(f (e_{4} ) = k + 5\), \(f (e_{5} ) = k + 9\). The induced vertex labels are k + 8, k + 10, 2k + 14.
For C2k+1 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 2k + 1]\). Define f by \(f (e_{1} ) = 4\), \(f (e_{2i} ) = k + 5 – i and f (e_{2i+1} ) = k + 9 + i\), for i ∈ \([1, k]\). The edge labels are:
4; k + 4, k + 3, . . . , 5; k + 10, k + 11, . . . , 2k + 9.
The induced vertex labels are: \(f^{+}(e_{2i} \cap e_{2i+1} ) = 2k + 14\), i ∈ \([1, k]\) , + \(f (e_{2i+1} \cap e_{2i+2} ) = 2k + 13\), i ∈ \([1, k – 1]\) , \(f^{+}(e_{1} \cap e_{2} ) = 4 + k + 4 = k + 8\), \(f^{+}(e_{1} \cap e_{2k+1} ) = 4 + 2k + 9 = 2k + 13\).
Therefore, f is a local antimagic labeling of \(C_{3} + C_{5} + C_{2k+1}\) with induced vertex labels k + 8, k + 10, 2k + 13, 2k + 14. Next, we construct a local antimagic 4-coloring of \(C_{3} + C_{5} + C_{2k}\) for k ≥ 2. Note that there are 2k + 8 edges. For C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = 2\), \(f (e_{2} ) = 2k + 5\), \(f (e_{3} ) = 2k + 7\). The induced vertex labels are 2k + 7, 2k + 9, 4k + 12. For C5 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 5]\). Define f by \(f (e_{1} ) = 1\), \(f (e_{2} ) = 2k + 6\), \(f (e_{3} ) = 3\), \(f (e_{4} ) = 2k + 4\), \(f (e_{5} ) = 2k + 8\). The induced vertex labels are 2k + 7, 2k + 9, 4k + 12. For C2k , let ei be the i-th edge in the clockwise order for i ∈ \([1, 2k]\). Define f by \(f (e_{2i-1} ) = 2i + 2 and f (e_{2i} ) = 2k + 5 – 2i\), for i ∈ \([1, k]\). The edge labels are:
4, 6, . . . , 2k + 2; 2k + 3, 2k + 1, . . . , 5.
The induced vertex labels are: \(f^{+}(e_{2i-1} \cap e_{2i} ) = 2k + 7\), i ∈ \([1, k]\) , \(f^{+}(e_{2i} \cap e_{2i+1} ) = 2k + 9\), i ∈ \([1, k – 1]\) , + \(f (e_{1} \cap e_{2k} ) = 4 + 5 = 9\).
Therefore, f is a local antimagic labeling of \(C_{3} + C_{5} + C_{2k}\) with induced vertex labels 9, 2k + 7, 2k + 9, 4k + 12. Combining the above results, we have 3 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{5} + C_{a} ) \leq 4 for a \geq 3\).
Below we provide some families of graphs belonging to \(C_{3} +C_{5} +C_{a}\) with local antimagic chromatic number 3.
Theorem 6.2. For k ≥ 1, \(\chi_{\mathrm{la}} (C_{3} + C_{5} + C_{8k+2} ) = 3\).
Proof. By Theorem 6.1, 3 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{5} + C_{8k+2} ) \leq 4\). We construct a local antimagic 3-coloring of \(C_{3} + C_{5} + C_{8k+2}\) for k ≥ 1. Note that there are 8k + 10 edges.
For C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = 4k +3\), \(f (e_{2} ) = 4k +8\), \(f (e_{3} ) = 4k +5\). The induced vertex labels are 8k +8, 8k +11, 8k +13. For C5 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 5]\). Define f by \(f (e_{1} ) = 4k + 2\), \(f (e_{2} ) = 4k + 9\), \(f (e_{3} ) = 4k + 4\), \(f (e_{4} ) = 4k + 7\), \(f (e_{5} ) = 4k + 6\). The induced vertex labels are 8k + 8, 8k + 11, 8k + 13. For C8k+2 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 8k + 2]\). Define f by \(f (e_{1} ) = 1\), \(f (e_{4k+2} ) = 4k + 10\), and for i ∈ \([0, k – 1]\), 8k + 10 − 4i, i even (≡ 2 mod 8), ( \(f (e_{4i+2} ) = 8k + 7 – 4i\), i odd (≡ 3 mod 8), 3 + 4i, i even (≡ 3 mod 8), ( \(f (e_{4i+3} ) = 4 + 4i\), i odd (≡ 0 mod 8), 8k + 8 − 4i, i even (≡ 0 mod 8), ( \(f (e_{4i+4} ) = 8k + 9 – 4i\), i odd (≡ 5 mod 8), 5 + 4i, i even (≡ 5 mod 8), ( \(f (e_{4i+5} ) = 2 + 4i\), i odd (≡ 6 mod 8), 8k + 7 − 4i, i even (≡ 7 mod 8), ( \(f (e_{8k+2}-4i ) = 8k + 10 – 4i\), i odd (≡ 6 mod 8), 4 + 4i, i even (≡ 4 mod 8), ( \(f (e_{8k+1}-4i ) = 3 + 4i\), i odd (≡ 7 mod 8), 8k + 9 − 4i, i even (≡ 1 mod 8), ( \(f (e_{8k}-4i ) = 8k + 8 – 4i\), i odd (≡ 4 mod 8), 2 + 4i, i even (≡ 2 mod 8), ( \(f (e_{8k-1}-4i ) = 5 + 4i\), i odd (≡ 1 mod 8). Note that (1) 4i + 2 ≥ 2 and 8k + 10 − 4i ≤ 8k + 10. (2) 5 + 4i ≤ 5 + 4(k − 1) = 4k + 1 and 8k + 7 − 4i ≥ 8k + 7 − 4(k − 1) = 4k + 11. (3) By considering mod 8, if two edge labels are equal, then either 8k + a − 4i = a − 4 + 4i′ =⇒ i + i′ = 2k + 1 or 8k + b − 4i = b − 8 + 4i′ =⇒ i + i′ = 2k + 2. Both are impossible. Thus all edge labels are distinct. (4) \(f^{+}(e_{1} \cap e_{2} ) = 1 + 8k + 10 = 8k + 11 and f^{+}(e_{1} \cap e_{8k+2} ) = 1 + 8k + 7 = 8k + 8\). (5) For i ∈ \([0, k – 1]\), 8k + 13, i even, ( \(f^{+}(e_{4i+2} \cap e_{4i+3} ) = 8k + 11\), i odd, 8k + 11, i even, ( \(f^{+}(e_{4i+3} \cap e_{4i+4} ) = 8k + 13\), i odd, 8k + 13, i even, ( \(f^{+}(e_{4i+4} \cap e_{4i+5} ) = 8k + 11\), i odd, 8k + 11, i even, ( \(f^{+}(e_{8k+2}-4i \cap e_{8k+1}-4i ) = 8k + 13\), i odd, 8k + 13, i even, ( \(f^{+}(e_{8k+1}-4i \cap e_{8k}-4i ) = 8k + 11\), i odd, 8k + 11, i even, ( \(f^{+}(e_{8k}-4i \cap e_{8k-1}-4i ) = 8k + 13\), i odd.
For i ∈ \([0, k – 2]\), 8k + 8, i even, ( \(f^{+}(e_{4i+5} \cap e_{4i+6} ) = 8k + 8\), i odd, 8k + 8, i even, ( \(f^{+}(e_{8k-1}-4i \cap e_{8k-2}-4i ) = 8k + 8\), i odd.
(6) When k is odd, \(f^{+}(e_{4k+1} \cap e_{4k+2} ) = 5 + 4(k – 1) + 4k + 10 = 8k + 11 and f^{+}(e_{4k+2} \cap e_{4k+3} ) = 4k + 10 + 2 + 4(k – 1) = 8k + 8\). When k is even, \(f^{+}(e_{4k+1} \cap e_{4k+2} ) = 2 + 4(k – 1) + 4k + 10 = 8k + 8 and f^{+}(e_{4k+2} \cap e_{4k+3} ) = 4k + 10 + 5 + 4(k – 1) = 8k + 11\). Therefore, f is a local antimagic labeling of \(C_{3} + C_{5} + C_{8k+2}\) with induced vertex labels 8k + 8, 8k + 11, 8k + 13.
Theorem 6.3. For k ≥ 1, \(\chi_{\mathrm{la}} (C_{3} + C_{5} + C_{8k+14} ) = 3\).
Proof. By Theorem 6.1, 3 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{5} + C_{8k+14} ) \leq 4\). We construct a local antimagic 3-coloring of \(C_{3} + C_{5} + C_{8k+14}\) for k ≥ 1. Note that there are 8k + 22 edges. For C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = 4k + 9\), \(f (e_{2} ) = 4k + 14\), \(f (e_{3} ) = 4k + 11\). The induced vertex labels are 8k + 20, 8k + 23, 8k + 25. For C5 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 5]\). Define f by \(f (e_{1} ) = 4k + 8\), \(f (e_{2} ) = 4k + 15\), \(f (e_{3} ) = 4k + 10\), \(f (e_{4} ) = 4k + 13\), \(f (e_{5} ) = 4k + 12\). The induced vertex labels are 8k + 20, 8k + 23, 8k + 25. For C8k+14 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 8k + 14]\). Define f by \(f (e_{1} ) = 1\), \(f (e_{2} ) = 8k + 22\), \(f (e_{3} ) = 3\), \(f (e_{4} ) = 8k + 20\), \(f (e_{5} ) = 5\), \(f (e_{6} ) = 8k + 15\), \(f (e_{7} ) = 10\), \(f (e_{8} ) = 8k + 13\), \(f (e_{9} ) = 7\), \(f (e_{10} ) = 8k + 18\), \(f (e_{11} ) = 2\), \(f (e_{12} ) = 8k + 21\), \(f (e_{13} ) = 4\), \(f (e_{14} ) = 8k+16\), \(f (e_{15} ) = 9\), \(f (e_{16} ) = 8k+14\), \(f (e_{17} ) = 11\), \(f (e_{4k+14} ) = 4k+16\), \(f (e_{8k+11} ) = 8\), \(f (e_{8k+12} ) = 8k + 17\), \(f (e_{8k+13} ) = 6\), \(f (e_{8k+14} ) = 8k + 19\). The edge labels are 1, 2, . . . , 11; 4k + 16; 8k + 13, 8k + 14, . . . , 8k + 22. The induced vertex labels are 8k + 20, 8k + 23, 8k + 25.
For i ∈ \([0, k – 2]\), i even (≡ 1 mod 8), ( 8k + 9 − 4i, \(f (e_{4i+18} ) = 8k + 12 – 4i\), i odd (≡ 0 mod 8), 14 + 4i, i even (≡ 6 mod 8), ( \(f (e_{4i+19} ) = 13 + 4i\), i odd (≡ 1 mod 8), 8k + 11 − 4i, i even (≡ 3 mod 8), ( \(f (e_{4i+20} ) = 8k + 10 – 4i\), i odd (≡ 6 mod 8), 12 + 4i, i even (≡ 4 mod 8), ( \(f (e_{4i+21} ) = 15 + 4i\), i odd (≡ 3 mod 8), 8k + 12 − 4i, i even (≡ 4 mod 8), ( \(f (e_{8k+10}-4i ) = 8k + 9 – 4i\), i odd (≡ 5 mod 8), 13 + 4i, i even (≡ 5 mod 8), ( \(f (e_{8k+9}-4i ) = 14 + 4i\), i odd (≡ 2 mod 8), 8k + 10 − 4i, i even (≡ 2 mod 8), ( \(f (e_{8k+8}-4i ) = 8k + 11 – 4i\), i odd (≡ 7 mod 8), 15 + 4i, i even (≡ 7 mod 8), ( \(f (e_{8k+7}-4i ) = 12 + 4i\), i odd (≡ 0 mod 8).
Note that (1) 12 + 4i ≥ 12 and 8k + 12 − 4i ≤ 8k + 12. (2) 15 + 4i ≤ 15 + 4(k − 2) = 4k + 7 and 8k + 9 − 4i ≥ 8k + 9 − 4(k − 2) = 4k + 17. (3) By considering mod 8, if two edge labels are equal, then either 8k + a − 4i = a + 4 + 4i′ =⇒ i + i′ = 2k − 1 or 8k + 12 − 4i = 12 + 4i′ =⇒ i + i′ = 2k . Both are impossible. Thus all edge labels are distinct. (4) \(f^{+}(e_{17} \cap e_{18} ) = 11 + 8k + 9 = 8k + 20 and f^{+}(e_{8k+10} \cap e_{8k+11} ) = 8k + 12 + 8 = 8k + 20\). (5) For i ∈ \([0, k – 2]\), 8k + 23, i even, ( \(f^{+}(e_{4i+18} \cap e_{4i+19} ) = 8k + 25\), i odd, 8k + 25, i even, ( \(f^{+}(e_{4i+19} \cap e_{4i+20} ) = 8k + 23\), i odd, 8k + 23, i even, ( \(f^{+}(e_{4i+20} \cap e_{4i+21} ) = 8k + 25\), i odd, 8k + 25, i even, ( \(f^{+}(e_{8k+10}-4i \cap e_{8k+9}-4i ) = 8k + 23\), i odd, 8k + 23, i even, ( \(f^{+}(e_{8k+9}-4i \cap e_{8k+8}-4i ) = 8k + 25\), i odd, 8k + 25, i even, ( \(f^{+}(e_{8k+8}-4i \cap e_{8k+7}-4i ) = 8k + 23\), i odd.
For i ∈ \([0, k – 3]\), 8k + 20, i even, ( \(f^{+}(e_{4i+21} \cap e_{4i+22} ) = 8k + 20\), i odd. 8k + 20, i even, ( \(f^{+}(e_{8k+7}-4i \cap e_{8k+6}-4i ) = 8k + 20\), i odd.
(6) When k is even, \(f^{+}(e_{4k+13} \cap e_{4k+14} ) = 12 + 4(k – 2) + 4k + 16 = 8k + 20 and f^{+}(e_{4k+14} \cap e_{4k+15} ) = 4k + 16 + 15 + 4(k – 2) = 8k + 23\). When k is odd, \(f^{+}(e_{4k+13} \cap e_{4k+14} ) = 15 + 4(k – 2) + 4k + 16 = 8k + 23 and f^{+}(e_{4k+14} \cap e_{4k+15} ) = 4k + 16 + 12 + 4(k – 2) = 8k + 20\). Therefore, f is a local antimagic labeling of \(C_{3} + C_{5} + C_{8k+14}\) with induced vertex labels 8k + 20, 8k + 23, 8k + 25.
Combining Theorem 6.2, Theorem 6.3 and Theorem 4.1 (with k = 1), we have
Theorem 6.4. For k ≥ 1 and k ̸= 3, \(\chi_{\mathrm{la}} (C_{3} + C_{5} + C_{4k+2} ) = 3\).
By using computer, we have checked that \(\chi_{\mathrm{la}} (C_{3} + C_{5} + C_{14} ) = 4\). (Refer to Appendix)
Theorem 7.1. For k ≥ 1, \(\chi_{\mathrm{la}} (C_{3} + C_{4k+1} + C_{4k+5} ) = 3\).
Proof. By Theorem 1.1, 3 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{4k+1} + C_{4k+5} ) \leq 5\). We construct a local antimagic 3-coloring of \(C_{3} + C_{4k+1} + C_{4k+5}\) for k ≥ 1. Note that there are 8k + 9 edges. For C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = 2k+2\), \(f (e_{2} ) = 6k+8\), \(f (e_{3} ) = 4k+4\). The induced vertex labels are 6k+6, 8k+10, 10k+12. For C4k+1 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 4k + 1]\). Define f by \(f (e_{4k+1} ) = 4k + 6\), and for i ∈ \([1, k]\), \(f (e_{4i-3} ) = 2k + 2 – 2i\), \(f (e_{4i-2} ) = 6k + 8 + 2i\), \(f (e_{4i-1} ) = 4k + 4 – 2i\), \(f (e_{4i} ) = 4k + 6 + 2i\). The edge labels are 2k, 2k − 2, . . . , 2; 6k + 10, 6k + 12, . . . , 8k + 8; 4k + 2, 4k, . . . , 2k + 4; 4k + 8, 4k + 10, . . . , 6k + 6; 4k + 6, which are all the even integers in \([1, 8k + 9]\) except 2k + 2, 4k + 4, 6k + 8.
For i ∈ \([1, k]\), \(f^{+}(e_{4i-3} \cap e_{4i-2} ) = 8k + 10\), \(f^{+}(e_{4i-2} \cap e_{4i-1} ) = 10k + 12\), \(f^{+}(e_{4i-1} \cap e_{4i} ) = 8k + 10\).
For i ∈ \([1, k – 1]\), \(f^{+}(e_{4i} \cap e_{4i+1} ) = 6k + 6\), \(f^{+}(e_{4k} \cap e_{4k+1} ) = 6k + 6 + 4k + 6 = 10k + 12\), \(f^{+}(e_{4k+1} \cap e_{1} ) = 4k + 6 + 2k = 6k + 6\). For C4k+5 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 4k + 5]\). Define f by \(f (e_{4k+5} ) = 4k + 5\), and for i ∈ \([1, k + 1]\), \(f (e_{4i-3} ) = 2k + 3 – 2i\), \(f (e_{4i-2} ) = 6k + 7 + 2i\), \(f (e_{4i-1} ) = 4k + 5 – 2i\), \(f (e_{4i} ) = 4k + 5 + 2i\).
The edge labels are 2k +1, 2k −1, . . . , 1; 6k +9, 6k +11, . . . , 8k +9; 4k +3, 4k +1, . . . , 2k + 3; 4k + 7, 4k + 9, . . . , 6k + 7; 4k + 5, which are all the odd integers in \([1, 8k + 9]\). For i ∈ \([1, k + 1]\), \(f^{+}(e_{4i-3} \cap e_{4i-2} ) = 8k + 10\), \(f^{+}(e_{4i-2} \cap e_{4i-1} ) = 10k + 12\), \(f^{+}(e_{4i-1} \cap e_{4i} ) = 8k + 10\).
For i ∈ \([1, k]\), \(f^{+}(e_{4i} \cap e_{4i+1} ) = 6k + 6\), \(f^{+}(e_{4k+4} \cap e_{4k+5} ) = 6k + 7 + 4k + 5 = 10k + 12\), \(f^{+}(e_{4k+5} \cap e_{1} ) = 4k + 5 + 2k + 1 = 6k + 6\). Therefore, f is a local antimagic labeling of \(C_{3} + C_{4k+1} + C_{4k+5}\) with induced vertex labels 6k + 6, 8k + 10, 10k + 12.
Theorem 7.2. For k ≥ 1, \(\chi_{\mathrm{la}} (C_{3} + C_{4k+1} + C_{4k+6} ) = 3\).
Proof. By Theorem 1.1, 3 ≤ \(\chi_{\mathrm{la}} (C_{3} + C_{4k+1} + C_{4k+6} ) \leq 5\). We construct a local antimagic 3-coloring of \(C_{3} + C_{4k+1} + C_{4k+6}\) for k ≥ 1. Note that there are 8k + 10 edges. For C3 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 3]\). Define f by \(f (e_{1} ) = 3k +4\), \(f (e_{2} ) = 5k +7\), \(f (e_{3} ) = 4k +5\). The induced vertex labels are 7k +9, 8k +11, 9k +12. For C4k+1 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 4k + 1]\). Define f by \(f (e_{4k+1} ) = 4k + 6\), and for i ∈ \([1, k]\), \(f (e_{4i-3} ) = 3k + 4 – i\), \(f (e_{4i-2} ) = 5k + 7 + i\), \(f (e_{4i-1} ) = 4k + 5 – i\), \(f (e_{4i} ) = 4k + 6 + i\).
The edge labels are 3k + 3, 3k + 2, . . . , 2k + 4; 5k + 8, 5k + 9, . . . , 6k + 7; 4k + 4, 4k + 3, . . . , 3k + 5; 4k + 7, 4k + 8, . . . , 5k + 6; 4k + 6, which are all the integers in \([2k + 4, 6k + 7]\) except 3k + 4, 4k + 5, 5k + 7. For i ∈ \([1, k]\), \(f^{+}(e_{4i-3} \cap e_{4i-2} ) = 8k + 11\), \(f^{+}(e_{4i-2} \cap e_{4i-1} ) = 9k + 12\), \(f^{+}(e_{4i-1} \cap e_{4i} ) = 8k + 11\).
For i ∈ \([1, k – 1]\), \(f^{+}(e_{4i} \cap e_{4i+1} ) = 7k + 9\), \(f^{+}(e_{4k} \cap e_{4k+1} ) = 5k + 6 + 4k + 6 = 9k + 12 and f^{+}(e_{4k+1} \cap e_{1} ) = 4k + 6 + 3k + 3 = 7k + 9\). For C4k+6 , let ei be the i-th edge in the clockwise order for i ∈ \([1, 4k + 6]\). Define f by \(f (e_{4k+5} ) = 2k + 3\), \(f (e_{4k+6} ) = 6k + 8\), and for i ∈ \([1, k + 1]\), \(f (e_{4i-3} ) = k + 2 – i\), \(f (e_{4i-2} ) = 7k + 9 + i\), \(f (e_{4i-1} ) = 2k + 3 – i\), \(f (e_{4i} ) = 6k + 8 + i\).
The edge labels are k +1, k −1, . . . , 1; 7k +10, 7k +11, . . . , 8k +10; 2k +2, 2k +1, . . . , k + 2; 6k + 9, 6k + 10, . . . , 7k + 9; 2k + 3; 6k + 8, which are all the integers in \([1, 2k + 3]\) ∪ \([6k + 8, 8k + 10]\). For i ∈ \([1, k + 1]\), \(f^{+}(e_{4i-3} \cap e_{4i-2} ) = 8k + 11\), \(f^{+}(e_{4i-2} \cap e_{4i-1} ) = 9k + 12\), \(f^{+}(e_{4i-1} \cap e_{4i} ) = 8k + 11\).
For i ∈ \([1, k]\), \(f^{+}(e_{4i} \cap e_{4i+1} ) = 7k + 9\), \(f^{+}(e_{4k+4} \cap e4k+5 ) = 7k +9+2k +3 = 9k +12\), \(f^{+}(e_{4k+5} \cap e4k+6 ) = 2k +3+6k +8 = 8k +11\), \(f^{+}(e_{4k+6} \cap e_{1} ) = 6k + 8 + k + 1 = 7k + 9\). Therefore, f is a local antimagic labeling of \(C_{3} + C_{4k+1} + C_{4k+6}\) with induced vertex labels 7k + 9, 8k + 11, 9k + 12.
Summing up, the main results of this paper are:
(1) \(\chi_{\mathrm{la}} (C_{3} + C_{3} + C_{3} ) = 5 and \chi_{\mathrm{la}} (C_{3} + C_{3} + C_{k}\)) = 4 for k ≥ 4. (2) \(\chi_{\mathrm{la}} (C_{3} + C_{4} + C_{2k+1} ) = 4\). (3) \(\chi_{\mathrm{la}} (C_{3} + C_{5} + C_{14} ) = 4 and \chi_{\mathrm{la}} (C_{3} + C_{5} + C_{4k+2}\)) = 3 for k ̸= 3. (4) \(\chi_{\mathrm{la}} (C_{3} + C_{6} + C_{4k+1} ) = 3\); \(\chi_{\mathrm{la}} (C_{3} + C_{10} + C_{8k-3} ) = 3\); \(\chi_{\mathrm{la}} (C_{3} + C_{4k+1} + C_{4k+5} ) = 3 and \chi_{\mathrm{la}} (C_{3} + C_{4k+1} + C_{4k+6}\)) = 3. The next reachable goal is to determine \(\chi_{\mathrm{la}} (C_{3} + C_{5} + C_{4k} )\), \(\chi_{\mathrm{la}} (C_{3} + C_{5} + C_{2k+1} )\) and \(\chi_{\mathrm{la}} (C_{3} + C_{6} + C_{4k+3} )\). Future directions include studying local antimagic labeling of \(C_{3} + C_{a} + C_{2k}\) and \(C_{3} + C_{a} + C_{2k+1}\) where a ≥ 7. This may not be easy as there are no general methods of constructing such labelings. Even more challenging questions concern local antimagic labeling of \(C_{a} + C_{b} + C_{2k}\) and \(C_{a} + C_{b} + C_{2k+1}\) where both a, b are odd integers greater than 3.
Here we give an algorithm to verify that \(\chi_{\mathrm{la}} (C_{3} + C_{5} + C_{14} )\) ̸= 3. First, we derive some useful results on the edge labels and induced vertex labels of \(C_{3} + C_{5} + C_{2k}\) if \(\chi_{\mathrm{la}} (C_{3} + C_{5} + C_{2k} ) = 3\). Let f be a local antimagic 3-coloring of \(C_{3} + C_{5} + C_{2k}\) . Denote the induced vertex labels of \(C_{3} + C_{5} + C_{2k}\) by a, b, c. By Lemma 3.2, let a = 2k + 9 and b < a < c. The edge labels on C3 are a+b−c 2 , b+c−a 2 , c+a−b 2 . We have a + b ≡ c (mod 2), b + c ≡ a (mod 2), c + a ≡ b (mod 2). So one of b, c is odd and the other is even. By Lemma 2.2, we can assume that b is odd and c is even. Also, (1) a + b > c.
Algorithm 1. Check whether \(\chi_{\mathrm{la}}(C_3+C_5+C_{2k})=3\)
a = 2k + 9
for odd integer b in [3, 2k + 7] do
for even integer c in [2k + 10, 4k + 14] do
Set all integers in [1, 2k + 8] as available
Set f(e_i) = 0, f⁺(u_i) = 0 for all i ∈ [1, 2k]
Set p(i) = 0 for all i ∈ [1, 2k] ▷ p(i) allows the vertex label of u_i to go through a, b, c
if a, b, c satisfy conditions (1), (2) and (3) then
Set v(0) = a, v(1) = b, v(2) = c
Set (a+b−c)/2, (b+c−a)/2, (c+a−b)/2 as unavailable
Set c/2, a−c/2, b−a+c/2, a−b+c/2, b−c/2 as unavailable
Find the smallest available edge label d for C_{2k}
for (f⁺(u_1), f⁺(u_2)) in {(a,b), (a,c), (b,c)} do
if d < f⁺(u_1) and d < f⁺(u_2) then
f(e_1) = d and set f(e_1) as unavailable
if f⁺(u_2) − d is available then
f(e_2) = f⁺(u_2) − d and set f(e_2) as unavailable
i = 3 ▷ u_i is the current vertex under consideration
while i > 2 do
if i ≤ 2k then
if p(i) ≤ 2 then
if p(i) ≠ p(i−1) and v(p(i)) > f(e_{i−1}) and
v(p(i)) − f(e_{i−1}) is available then
f⁺(u_i) = v(p(i))
f(e_i) = f⁺(u_i) − f(e_{i−1}) and set f(e_i) as unavailable
i++
else
p(i)++
end if
else
p(i) = 0
i−−
Set f(e_i) as available
p(i)++
end if
else
if f(e_{2k}) + f(e_1) = f⁺(u_1) then
Print out the local antimagic 3-coloring f of C_3 + C_5 + C_{2k}
end if
i−−
Set f(e_i) as available
p(i)++
end if
end while
end if
end if
end for
end if
end for
end forBy considering all possible arrangements of the induced vertex labels of \(C_5\), each one has the pattern \(x,y,x,y,z\) in cyclic order where \(\{x,y,z\}=\{a,b,c\}\). Solving the following system of linear equations \[ \begin{bmatrix} 1&1&0&0&0\\ 0&1&1&0&0\\ 0&0&1&1&0\\ 0&0&0&1&1\\ 1&0&0&0&1 \end{bmatrix} \begin{bmatrix}e_1\\e_2\\e_3\\e_4\\e_5\end{bmatrix} = \begin{bmatrix}x\\y\\z\\x\\y\end{bmatrix}, \] the edge labels of \(C_5\) are \(\frac{z}{2}\), \(x-\frac{z}{2}\), \(y-x+\frac{z}{2}\), \(x-y+\frac{z}{2}\), \(y-\frac{z}{2}\) in cyclic order. Hence, \(z=c\). Therefore, the edge labels of \(C_5\) are \(\frac{c}{2}\), \(a-\frac{c}{2}\), \(b-a+\frac{c}{2}\), \(a-b+\frac{c}{2}\), \(b-\frac{c}{2}\) in cyclic order which satisfy (2) \(b>\frac{c}{2}\) and \(b-a+\frac{c}{2}>0\).
Since all the edge labels on \(C_3\) and \(C_5\) are distinct, we have (3) \(\frac{b+c-a}{2}\neq a-\frac{c}{2}\Longleftrightarrow b+2c\neq3a\).
Algorithm 1 is the pseudocode for checking whether \(\chi_{\mathrm{la}}(C_3+C_5+C_{2k})=3\). Denote \(C_{2k}=u_1u_2\cdots u_{2k}u_1\) where \(e_i=u_iu_{i+1}\) for \(i\in[1,2k]\) and \(u_{2k+1}=u_1\).