An edge-coloring of a graph \(G\) with natural numbers \(1,2,\ldots\) is called a sum edge-coloring if the colors of edges incident to any vertex of \(G\) are distinct and the sum of the colors of the edges of \(G\) is minimum. The edge-chromatic sum of a graph \(G\) is the sum of the colors of edges in a sum edge-coloring of \(G\). In general, the problem of finding the edge-chromatic sum of an \(r\)-regular (\(r\geq 3\)) graph is \(NP\)-complete. In this paper we provide some bounds on the edge-chromatic sums of various products of graphs. In particular, we give tight upper bounds on the edge-chromatic sums of tensor, strong tensor, Cartesian, strong products and composition of graphs. We also determine the edge-chromatic sums and edge-strengths of the Cartesian products of regular graphs and paths (cycles) with an even number of vertices. Finally, we determine the edge-chromatic sums and edge-strengths of grids, cylinders, and tori.
We use [11, 28] for terminology and notation not defined here. We consider finite undirected graphs that do not contain loops or multiple edges. Let \(V(G)\) and \(E(G)\) denote the sets of vertices and edges of \(G\), respectively. A graph \(G=(V,E)\) is called an \((n, m)\)-graph if \(|V| = n\) and \(|E| = m\). The complement of a graph \(G\) is denoted by \(\overline{G}\). The set of neighbors of a vertex \(v\) in \(G\) is denoted by \(N_{G}(v)\). The degree of a vertex \(v\in V(G)\) is denoted by \(d_{G}(v)\), the maximum degree of vertices in \(G\) by \(\Delta(G)\), the chromatic number of \(G\) by \(\chi(G)\), and the chromatic index of \(G\) by \(\chi^{\prime}(G)\).
A proper vertex coloring of a graph \(G\) is a mapping \(\alpha: V(G)\rightarrow \mathbb{N}\) such that \(\alpha(u)\neq \alpha(v)\) for every \(uv\in E(G)\). If \(\alpha\) is a proper vertex coloring of a graph \(G\), then \(\Sigma(G,\alpha)\) denotes the sum of the colors of the vertices of \(G\).
For a graph \(G\), define the chromatic sum \(\Sigma(G)\) as follows: \(\Sigma(G)=\min_{\alpha}\Sigma(G,\alpha)\), where minimum is taken over all possible proper vertex colorings of \(G\). If \(\alpha\) is a proper vertex coloring of a graph \(G\) and \(\Sigma(G)=\Sigma(G,\alpha)\), then \(\alpha\) is called a sum coloring. The strength of a graph \(G\), denoted by \(s(G)\), is the minimum number of colors needed for a sum coloring of \(G\). Clearly, \(s(G)\geq \chi(G)\) for any graph \(G\). The concept of sum coloring and chromatic sum was introduced by Kubicka [17] and Supowit [26]. In [20] Kubicka and Schwenk showed that the problem of finding the chromatic sum is \(NP\)-complete in general and polynomial-time solvable for trees. In [27], Thomassen, Erdős, Alavi, Malde and Schwenk derived tight bounds on the chromatic sums of graphs. In particular, they proved that for any \((n,m)\)-graph \(G\), \(n\leq \Sigma(G)\leq n+m\). In [12], a dynamic programming algorithm for the problem of finding the chromatic sum of partial \(k\)-trees was suggested. In [3, 4, 8, 13, 19], approximation algorithms were given for the problem of finding the chromatic sum of various classes of graphs. The strength of graphs was considered in [6, 10, 15, 23]. In particular, Hajiabolhassan, Mehrabadi, and Tusserkani [10] showed that for any graph \(G\), \(s(G)\leq \left\lceil\frac{\Delta(G)+col(G)}{2}\right\rceil\), where \(col(G)\) is the coloring number of \(G\). They also proved Brooks’ like theorem for the strength of graphs: If \(G\) is a connected graph, then \(s(G) =\Delta(G)+1\) if and only if \(G\) is a complete graph or an odd cycle. On the other hand, there are graphs \(G\) with \(s(G)>\chi(G)\) [6]. In [23], Nicoloso derived a tight upper bound on the strength of interval graphs: for any interval graph \(G\), \(s(G)\leq 2\chi(G)-1\). Some interesting results on chromatic sums and strengths of graphs can be found in [15, 16, 18].
An edge version of the problem of finding the sum coloring and chromatic sum of graphs was suggested in [3, 9, 10]. In particular, in [3, 9, 10], the authors introduced the concept of sum edge-coloring and edge-chromatic sum of graphs. A proper edge-coloring of a graph \(G\) is a mapping \(\alpha: E(G)\rightarrow \mathbb{N}\) such that \(\alpha(e)\neq \alpha(e^{\prime})\) for every pair of adjacent edges \(e,e^{\prime}\in E(G)\). If \(\alpha\) is a proper edge-coloring of a graph \(G\), then \(\Sigma^{\prime}(G,\alpha)\) denotes the sum of the colors of the edges of \(G\). For a graph \(G\), define the edge-chromatic sum \(\Sigma^{\prime}(G)\) as follows: \(\Sigma^{\prime}(G)=\min_{\alpha}\Sigma^{\prime}(G,\alpha)\), where minimum is taken over all possible proper edge-colorings of \(G\). If \(\alpha\) is a proper edge-coloring of a graph \(G\) and \(\Sigma^{\prime}(G)=\Sigma^{\prime}(G,\alpha)\), then \(\alpha\) is called a sum edge-coloring. The edge-strength of a graph \(G\), denoted by \(s^{\prime}(G)\), is the minimum number of colors needed for a sum edge-coloring of \(G\). Clearly, \(s'(G)\geq \chi'(G)\) for any graph \(G\). In [10], Hajiabolhassan, Mehrabadi and Tusserkani proved Vizing’s like theorem for the edge-strength of graphs: for any graph \(G\), \(s'(G)\leq \Delta(G)+1\). In [3], Bar-Noy, Bellare, Halldorsson, Shachnai and Tamir showed that the problem of finding edge-chromatic sum is \(NP\)-hard for multigraphs. Moreover, in [9] it was shown that the problem remains \(NP\)-complete even for bipartite graphs with maximum degree \(3\). On the other hand, Giaro and Kubale [9] proved that the problem can be solved in polynomial-time for trees and \(s^{\prime}(G)=\chi^{\prime}(G)\) for any bipartite graph \(G\). In [25], Salavatipour proved that the problems of finding the edge-chromatic sum and the edge-strength are \(NP\)-complete for \(r\)-regular graphs (\(r\geq 3\)). Moreover, he also showed that \(s^{\prime}(G)=\chi^{\prime}(G)\) for any regular graph \(G\). Nevertheless, there are graphs \(G\) with \(\chi^{\prime}(G)=\Delta(G)\) and \(s^{\prime}(G)=\Delta(G)+1\) [10]. In [5], Cardinal, Ravelomanana and Valencia-Pabon determined the edge-strength of the multicycles. In [3, 4, 8, 13, 19], approximation algorithms were given for the problem of finding the edge-chromatic sum of various classes of graphs. A \(2\)-approximation algorithm for the problem was presented in [3]. For bipartite graphs and regular graphs \(2\) approximation ratio was improved to \(1.1414\) and \(1.375\), respectively, in [7, 24]. Some other interesting results on edge-chromatic sums and edge-strengths of graphs can be found in [9, 22, 24].
In this paper we study the problem of determining or bounding the edge-chromatic sums and edge-strengths of various products of graphs. In particular, we provide tight upper bounds on the edge-chromatic sums of tensor, strong tensor, Cartesian, strong products and composition of graphs. We also determine the edge-chromatic sums and edge-strengths of the Cartesian products of regular graphs and paths (cycles) with an even number of vertices. Finally, we determine the edge-chromatic sums and edge-strengths of meshes.
We use the standard notations \(P_{n}\), \(C_{n}\), \(K_{n}\) and \(Q_{n}\) for the path, cycle, complete graph on \(n\) vertices and the hypercube of dimension \(n\), respectively. A partial edge-coloring of a graph \(G\) is a coloring of some of the edges of \(G\) such that no two adjacent edges receive the same color. If \(\alpha\) is a partial edge-coloring of \(G\) and \(v\in V(G)\), then \(S\left(v,\alpha\right)\) denotes the set of colors appearing on colored edges incident to \(v\). If \(\alpha\) is a partial edge-coloring of a graph \(G\) and \(v\in V(G)\), then the smallest and largest colors of \(S\left(v,\alpha \right)\) are denoted by \(\underline S\left(v,\alpha \right)\) and \(\overline S\left(v,\alpha \right)\), respectively. Clearly, if \(\alpha\) is a proper edge-coloring of a graph \(G\), then \(\vert S(v,\alpha)\vert =d_G(v)\) for every \(v\in V(G)\). A proper edge-coloring \(\alpha\) of a graph \(G\) is a sequential coloring if for each vertex \(v\in V(G)\), \(S(v,\alpha)=\{1,2,\ldots,d_{G}(v)\}\) [1, 2].
Let \(G\) and \(H\) be graphs.
The Cartesian product of graphs \(G\) and \(H\) is a graph \(G \Box H\), where \(V(G \Box H) = V(G) \times V(H) = \{(u, v) |~u \in V(G), v \in V(H)\}\) and \(E(G \Box H) = \{(u, v_1)(u, v_2) | ~u\in V(G)\text{~and~}v_1v_2 \in E(H)\} \cup \{(u_1, v)(u_2, v) |~ u_1u_2 \in E(G)\text{~and~}v\in V(H)\}\).
The tensor (direct) product of graphs \(G\) and \(H\) is defined as a graph \(G \times H\), for which \(V(G \times H) = V(G) \times V(H)\) and \(E(G \times H) = \{(u_i, v_j)(u_l, v_k) | ~u_iu_l\in E(G) \;\text{~and~}\; v_jv_k\in E(H)\}.\)
The strong tensor product of graphs \(G\) and \(H\) is a graph \(G \otimes H\) for which \(V(G \otimes H) = V(G \times H)\) and \(E(G \otimes H) = E(G \times H) \cup \{(u_i, v_j)(u_l, v_j) |~u_iu_l\in E(G) \text{~and~} v_j \in V(H)\}\).
The strong product of graphs \(G\) and \(H\) is a graph \(G \boxtimes H\) for which \(V(G \boxtimes H) = V(G \otimes H)\) and \(E(G \boxtimes H) = E(G \otimes H) \cup \{(u_i, v_j)(u_i, v_l) |~u_i \in V(G) \text{~and~} v_jv_l \in E(H) \}\).
The composition (lexicographic product) of graphs \(G\) and \(H\) is a graph \(G[H]\) for which \(V(G[H])=V(G) \times V(H)\) and \(E(G[H])=\{(u_i, v_j)(u_l, v_k) |~u_iu_l \in E(G) \text{~or~} u_i=u_l \text{~and~} v_jv_k \in E(H)\}\).
We also need the following lemmas.
Lemma 2.1. For any graph \(G\), we have \(\sum{'}(G) \ge \frac{1}{4}\sum\limits_{v \in V(G)}{d_{G}(v)(d_{G}(v)+1)}\).
Proof. Let \(\alpha\) be a sum edge-coloring for \(G\). Clearly, for each \(v \in V(G)\), \(\sum\limits_{u \in N_G(v)}\alpha(vu) \ge 1 + 2 +\cdots+ d_{G}(v) = \frac{d_{G}(v)(d_{G}(v) + 1)}{2}\), since the colors on the edges incident to \(v\) are pairwise distinct natural numbers. On the other hand, \[\begin{split} \sum{'}(G) =& \sum\limits_{e \in E(G)}\alpha(e) = \frac{1}{2}\sum\limits_{v \in V(G)}\sum\limits_{u \in N_G(v)}\alpha(vu) \ge \frac{1}{2}\sum\limits_{v \in V(G)}\frac{d_{G}(v)(d_{G}(v) + 1)}{2} \\ =& \frac{1}{4}\sum\limits_{v \in V(G)}{d_{G}(v)(d_{G}(v)+1)}. \end{split}\] ◻
By Lemma 2.1, it can be easily obtained that for any graph \(G\) that admits a sequential coloring, \(\sum{'}(G) = \frac{1}{4}\sum\limits_{v \in V(G)}{d_{G}(v)(d_{G}(v)+1)}\). On the other hand, for a given graph \(G\), the problem of determining whether \(\sum{'}(G) = \frac{1}{4}\sum\limits_{v \in V(G)}{d_{G}(v)(d_{G}(v)+1)}\) or not is \(NP\)-complete [25].
Lemma 2.2. For an \((n, m)\)-graph \(G\) with \(s'(G) \ge 2\) and any \(k \in \mathbb{N}\) that satisfies \(2 \le k \le s'(G)\), we have \(\sum{'}(G) \ge k\left(m – \frac{k-1}{2}\left\lfloor\frac{n}{2}\right\rfloor\right).\)
Proof. Consider a sum edge-coloring that uses \(1,2,\ldots,s'(G)\) colors. For each \(1 \le i \le s'(G)\), let \(c_i\) denote the number of edges colored with color \(i\) in it. Clearly, for each \(1 \le i \le s'(G)\), \(c_i \le \left\lfloor\frac{n}{2}\right\rfloor\). This implies that
\[\begin{split} \sum{'}(G) =& \sum\limits_{i=1}^{s'(G)}i \cdot c_i = \sum\limits_{i=1}^ki \cdot c_i + \sum\limits_{i=k+1}^{s'(G)}i \cdot c_i \ge \sum\limits_{i=1}^k(k-(k-i)) \cdot c_i \\ &+\sum\limits_{i=k+1}^{s'(G)}k \cdot c_i =\sum\limits_{i=1}^kk \cdot c_i – \sum\limits_{i=1}^k(k-i) \cdot c_i + \sum\limits_{i=k+1}^{s'(G)}k \cdot c_i \\ =&km – \sum\limits_{i=1}^k(k-i) \cdot c_i \ge km – \sum\limits_{i=1}^k(k-i) \cdot \left\lfloor\frac{n}{2}\right\rfloor \\ =&k\left(m – \frac{k-1}{2}\left\lfloor\frac{n}{2}\right\rfloor\right). \end{split}\] ◻
We will also use the following results.
Theorem 2.3. [21] If for graphs \(G\) and \(H\), \(\chi'(G)=\Delta(G)\) or \(\chi'(H)=\Delta(H)\), then \(\chi'(G \Box H)=\Delta(G\Box H)\).
Theorem 2.5. [14] If \(G\) is a bipartite graph, then \(\chi'(G) = \Delta(G)\).
Theorem 2.6. [10] For every graph \(G\), \(s'(G) \le \Delta(G) + 1\).
We begin our considerations with an upper bound on the edge chromatic sums of tensor and strong tensor products of graphs with regular graphs.
Theorem 3.1. For any \((n, m)\)-graph \(G\) and an \(r\)-regular graph \(H\) of order \(p\) \((r \in \mathbb{N})\), we have \[\sum{'}(G \times H) \le rp\left(\sum{'}(G)r+\frac{(1-r)m}{2}\right).\]
Proof. Clearly, for the proof of Theorem 3.1, it is sufficient to construct a proper edge-coloring \(\alpha\) of \(G \times H\) for which the sum of colors on the edges is \(rp\left(\sum{'}(G)r+\frac{(1-r)m}{2}\right)\).
Let us now consider the graph \(K_2 \times H\). Let \(V(K_2 \times H) = \{(x, v_i) |~ v_i \in V(H)\} \cup \{(y, v_i) |~ v_i \in V(H)\}\) and \(E(K_2 \times H) = \{(x, v_i)(y, v_j) | ~v_iv_j\in E(H) \}\). Since \(K_2 \times H\) is a bipartite graph, by Theorem 2.5, \(\chi'(K_2 \times H)=\Delta(K_2 \times H)\) and hence there exists a proper edge-coloring of \(K_2 \times H\) with colors \(1,2,\ldots,\Delta(K_2 \times H)\). Since \(K_2 \times H\) is also \(r\)-regular, this coloring is also a sequential coloring, and thus is a sum edge-coloring with \(1,2,\dots,r\) colors. Let us denote it by \(\beta\). Also, let \(\gamma\) be a sum edge-coloring of \(G\) with colors \(1,2,\ldots,s'(G)\). Now we define an edge-coloring \(\alpha\) of \(G \times H\) as follows: for any \((u_i, v_j)(u_l, v_k) \in E(G \times H)\), let \[\alpha((u_i, v_j)(u_l, v_k)) = (\gamma(u_iu_l) – 1) \cdot r + \beta((x, v_j)(y, v_k)).\]
Clearly, \(\alpha\) is a proper edge-coloring of \(G \times H\) with colors \(1,2,\ldots,s'(G)r\). Moreover, it gives us the expected sum:
\[\begin{aligned} \sum\limits_{e \in E(G \times H)}\alpha(e) =& \sum\limits_{u_iu_l \in E(G)}\sum\limits_{v_jv_k \in E(H)}(\alpha((u_i, v_j)(u_l, v_k)) +\alpha((u_i, v_k)(u_l, v_j))) \\ =& 2\sum\limits_{v_jv_k \in E(H)}\sum\limits_{u_iu_l \in E(G)}(\gamma(u_iu_l) – 1) \cdot r \\ &+\sum\limits_{u_iu_l \in E(G)}\sum\limits_{v_jv_k \in E(H)}(\beta((x, v_j)(y, v_k)) + \beta((x, v_k)(y, v_j))) \\ =&r^2p\left(\sum{'}(G) – m\right) + m\sum{'}(K_2 \times H) \\ =&r^2p\left(\sum{'}(G) – m\right) + mp\frac{r(r+1)}{2} \\ =&rp\left(r\sum{'}(G)-\frac{rm}{2}+\frac{m}{2}\right). \end{aligned}\] ◻
Note that in some cases the coloring algorithm described in the proof above finds a sum edge-coloring:
Corollary 3.2. For any \((n, m)\)-graph \(G\) that admits a sequential coloring and an \(r\)-regular graph \(H\) of order \(p\) \((r \in \mathbb{N})\), we have \[\sum{'}(G \times H)=rp\left(\frac{r}{4}\sum\limits_{v \in V(G)}d_G^2(v) + \frac{m}{2}\right).\]
This corollary derives directly from Theorem 3.1 and Lemma 2.1. In particular, since all simple paths and cycles of even length admit sequential coloring, we have the following results:
Corollary 3.3. For any \(r\)-regular graph \(H\) of order \(p\) \((r \in \mathbb{N})\) and any \(n\in \mathbb{N}\), we have \[\sum{'}(P_{2n} \times H) = \frac{rp}{2}(4nr+2n-3r-1).\]
Corollary 3.4. For any \(r\)-regular graph \(H\) of order \(p\) \((r \in \mathbb{N})\) and any positive integer \(n\geq 2\), we have \[\sum{'}(C_{2n} \times H) = rp(2nr+n).\]
Next, we give a similar result for strong tensor products of graphs.
Theorem 3.5. For any \((n, m)\)-graph \(G\) and an \(r\)-regular graph \(H\) of order \(p\) \((r \in \mathbb{N})\), we have \[\sum{'}(G \otimes H) \le (r+1)p\left(\sum{'}(G)(r+1)-\frac{rm}{2}\right).\]
Proof. Similarly as in the previous theorem, it is sufficient to construct a proper edge-coloring \(\alpha\) of \(G \otimes H\) for which the sum of colors on the edges is \(p(r+1)\left((r+1)\sum{'}(G)-\frac{rm}{2}\right)\).
Let \(V(K_2 \otimes H) = \{(x, v_i) | ~v_i \in V(H)\} \cup \{(y, v_i) | ~v_i \in V(H)\}\) and \(E(K_2 \otimes H) = \{(x, v_i)(y, v_j) \;|\; v_iv_j \in E(H) \; \text{~or~} \; v_i=v_j \in V(H)\}\). Since it is a bipartite graph, by Theorem 2.5, \(\chi'(K_2 \otimes H)=\Delta(K_2 \otimes H)\), so there is a proper edge-coloring that uses only colors \(1, 2,\ldots,\Delta(K_2 \otimes H)\). Since \(K_2 \otimes H\) is \((r+1)\)-regular, this coloring is a sum edge-coloring with \(1,2,\ldots,r+1\) colors. Let us denote it by \(\beta\). Let \(\gamma\) be a sum edge-coloring of \(G\) that uses only colors \(1, 2,\ldots, s'(G)\). Now we construct an edge-coloring \(\alpha\) of \(G \otimes H\) as follows: for any \((u_i, v_j)(u_l, v_k) \in E(G \otimes H)\), let \[\alpha((u_i, v_j)(u_l, v_k)) = (\gamma(u_iu_l) – 1) \cdot (r + 1) + \beta((x, v_j)(y, v_k)).\]
Clearly, \(\alpha\) is a proper edge-coloring of \(G \otimes H\) with colors \(1,2,\ldots,s'(G)(r+1)\). Moreover, it gives us the expected sum: \[\begin{aligned} \sum\limits_{e \in E(G \otimes H)}\alpha(e) =& \sum\limits_{u_iu_l \in E(G)}\sum\limits_{v_jv_k \in E(H)}(\alpha((u_i, v_j)(u_l, v_k)) + \alpha((u_i, v_k)(u_l, v_j))) \\ &+\sum\limits_{u_iu_l \in E(G)}\sum\limits_{v_j \in V(H)}\alpha((u_i, v_j)(u_l, v_j)) \\ =& 2\sum\limits_{v_jv_k \in E(H)}\sum\limits_{u_iu_l \in E(G)}(\gamma(u_iu_l) – 1) \cdot (r + 1)\\ &+\sum\limits_{v_j \in V(H)}\sum\limits_{u_iu_l \in E(G)}(\gamma(u_iu_l) – 1) \cdot (r + 1) \\ &+\sum\limits_{u_iu_l \in E(G)}\sum\limits_{v_jv_k \in E(H)}(\beta((x, v_j)(y, v_k)) + \beta((x, v_k)(y, v_j))) \\ &+\sum\limits_{u_iu_l \in E(G)}\sum\limits_{v_j \in V(H)}\beta((x, v_j)(y, v_j))\\& =(pr+p)(r+1)\cdot \left(\sum{'}(G) – m\right) + m\sum{'}(K_2 \times H) \\ =&(r+1)^2p\left(\sum{'}(G) – m\right)+ mp\frac{(r+1)(r+2)}{2} \\ =& (r+1)p\left((r+1)\sum{'}(G)-\frac{rm}{2}\right). \end{aligned}\] ◻
Note that in some cases the coloring algorithm described in the proof above finds a sum edge-coloring:
Corollary 3.6. For any \((n, m)\)-graph \(G\) that admits a sequential coloring and an \(r\)-regular graph \(H\) of order \(p\) \((r \in \mathbb{N})\), we have \[\sum{'}(G \otimes H)=(r+1)p\left(\frac{r+1}{4}\sum\limits_{v \in V(G)}d_G^2(v) + \frac{m}{2}\right).\]
This corollary derives directly from Theorem 3.5 and Lemma 2.1. In particular, since all simple paths and cycles of even length admit sequential coloring, we have the following results:
Corollary 3.7. For any \(r\)-regular graph \(H\) of order \(p\) \((r \in \mathbb{N})\) and any \(n\in \mathbb{N}\), we have \[\sum{'}(P_{2n} \otimes H) = \frac{(r+1)p}{2}(4nr+6n-3r-4).\]
Corollary 3.8. For any \(r\)-regular graph \(H\) of order \(p\) \((r \in \mathbb{N})\) and any positive integer \(n\geq 2\), we have \[\sum{'}(C_{2n} \otimes H) = (r+1)p(2nr+3n).\]
In this section we provide tight upper bounds on the edge-chromatic sums of strong products of graphs with regular graphs.
Theorem 3.9. For any \((n, m)\)-graph \(G\) and an \(r\)-regular graph \(H\) of order \(p\) \((r \in \mathbb{N})\), we have \[\sum{'}(G \boxtimes H) \le (r+1)p\left(\sum{'}(G)(r+1)-\frac{rm}{2}\right)+\frac{nrps'(G \otimes H)}{2}+n\sum{'}(H).\]
Proof. For the proof, we will construct a proper edge-coloring \(\alpha\) of \(G \boxtimes H\) with the sum of colors equal to the right-hand side of the inequality in the theorem description. Let \(\beta\) be a sum edge-coloring of \(G \otimes H\) using colors \(1, 2,\ldots, s'(G \otimes H)\). Let \(\gamma\) be a sum edge-coloring of \(H\) with colors \(1, 2,\ldots, s'(H)\). We construct an edge-coloring \(\alpha\) of \(G \boxtimes H\) as follows: for each edge \(e = (u_i, v_j)(u_l, v_k)\in E(G \boxtimes H)\), if \(e \in E(G \otimes H)\), then \(\alpha(e)=\beta(e)\), otherwise \(\alpha(e)=\max\limits_{v_l\in V(H)}\overline S\left((u_i, v_l),\beta \right)+\gamma(v_jv_k)\). Clearly, \(\alpha\) is a proper edge-coloring of \(G \boxtimes H\) with colors \(1,2,\ldots,s'(G)(r+1)+s'(H)\). Moreover, by Theorem 3.5, we obtain the following upper bound on the sum of colors: \[\begin{split} \sum_{e \in E(G \boxtimes H)}\alpha(e) =& \sum_{e \in E(G \otimes H)}\alpha(e) +\sum_{u_i \in V(G), v_jv_l \in E(H)}\alpha((u_i, v_j)(u_i, v_l)) \\ &\le (r+1)p\left(\sum{'}(G)(r+1)-\frac{rm}{2}\right) \\ &+n\sum_{v_jv_l\in E(H)}(s'(G \otimes H)+\gamma(v_jv_l)) \\ =&(r+1)p\left(\sum{'}(G)(r+1)-\frac{rm}{2}\right) \\ &+s'(G \otimes H)n\frac{rp}{2}+n\sum{'}(H). \end{split}\] ◻
Let us note that if both graphs \(G\) and \(H\) admit a sequential coloring, the coloring \(\alpha\) from the proof of Theorem 3.9 provides the exact value of the edge-chromatic sum of \(G \boxtimes H\):
Corollary 10. For any \((n, m)\)-graph \(G\) and an \(r\)-regular graph \(H\) of order \(p\) \((r \in \mathbb{N})\), if both \(G\) and \(H\) admit a sequential coloring, we have \[\sum{'}(G \boxtimes H) = \frac{(r+1)p}{4}\left((r+1)\sum\limits_{v \in V(G)}d_G^2(v) + 2(2r+1)m+rn\right).\]
Proof. Note that the colorings \(\alpha\) we used in the proofs of Theorems 3.5 and 3.9 become sequential when both \(G\) and \(H\) graphs have a sequential coloring, hence, \(G \boxtimes H\) admits a sequential coloring, which gives us the exact value of the edge-chromatic sum. ◻
In this section we consider the edge-chromatic sums of composition of graphs. We begin our consideration with the result on the edge-chromatic sum of composition of graphs with empty graphs.
Theorem 3.11. For any graph \(G\) and any \(n\in \mathbb{N}\), we have \[\sum{'}\left(G[\overline{K_n}]\right) \le n^3\sum{'}(G)-\frac{n^2(n-1)|E(G)|}{2}.\] Moreover, this upper bound is sharp.
Proof. For the proof, it is sufficient to construct a proper edge-coloring \(\alpha\) of \(G[\overline{K_n}]\) for which the sum of colors on the edges is \(n^3\sum{'}(G)-\frac{n^2(n-1)|E(G)|}{2}\). Let \(V(G[\overline{K_n}]) = \{(u_i, v_j)|~u_i\in V(G), 1 \le j \le n\}\) and \(E(G[\overline{K_n}])=\{(u_i, v_j)(u_l, v_k) |~ u_iu_l \in E(G), 1 \le j, k \le n\}\). Let \(\beta\) be a sum edge-coloring of \(G\) with colors \(1,2,\ldots,s'(G)\). We construct an edge-coloring \(\alpha\) of \(G[\overline{K_n}]\) as follows: for each \(u_iu_l \in E(G)\) and for \(j,k=1,2,\ldots,n\), let \[\alpha((u_i, v_j)(u_l, v_k)) = n\beta(u_iu_l)-((j+k-1) \mod n).\] Clearly, \(\alpha\) is a proper edge-coloring of \(G[\overline{K_n}]\) with colors \(1,2,\ldots,s'(G)n\), and the sum of colors on all the edges is \[\begin{split} \sum_{e\in E(G[\overline{K_n}])}\alpha(e) =&\sum_{1\le j, k\le n}\sum_{u_iu_l \in E(G)}n\beta(u_iu_l)\\ &-\sum_{u_iu_l\in E(G)}\sum_{1 \le j\le n}\sum_{1 \le k \le n}((j+k-1)\mod n) \\ =&\sum_{1\le j, k\le n}n\sum_{u_iu_l \in E(G)}\beta(u_iu_l) \\ &-\sum_{u_iu_l\in E(G)}\sum_{1 \le j\le n}\frac{n(n-1)}{2} \\ =&\sum_{1\le j, k\le n}n\sum{'}(G)-\sum_{u_iu_l\in E(G)}\frac{n^2(n-1)}{2} \\ =&n^3\sum{'}(G)-\frac{n^2(n-1)|E(G)|}{2}. \end{split}\]
Note that if \(G\) admits a sequential coloring, we can choose \(\beta\) as such a coloring, and in that case, \(\alpha\) would also be a sequential, and therefore, a sum edge-coloring of \(G[\overline{K_n}]\). ◻
Our next result concerns the edge-chromatic sums of composition of graphs with regular graphs.
Theorem 3.12. For any \((n, m)\)-graph \(G\) and an \(r\)-regular graph \(H\) of order \(p\), we have \[\sum{'}(G[H]) \le n\sum{'}(H)+\frac{nrp^2s'(G)}{2} +p^3\sum{'}(G)-\frac{p^2(p-1)m}{2}.\]
Moreover, this upper bound is sharp.
Proof. Similarly as in the previous theorem, it is sufficient to construct a proper edge-coloring \(\alpha\) of \(G[H]\) for which the sum of colors on the edges is less than or equal to the right-hand side of the inequality in the theorem description. Let \(V(G[H]) = \{(u_i, v_j)|~u_i\in V(G), 1 \le j \le p\}\) and \(E(G[H])=\{(u_i, v_j)(u_l, v_k) |~ u_iu_l \in E(G), 1 \le j, k \le p\} \cup \{(u_i, v_j)(u_i, v_k)|~u_i\in V(G), v_jv_k \in E(H)\}\). Let \(\beta\) be a sum edge-coloring of \(G\) with colors \(1,2,\ldots,s'(G)\) and \(\gamma\) be a sum edge-coloring of \(H\) with colors \(1,2,\ldots,s'(H)\). We construct an edge-coloring \(\alpha\) of \(G[H]\) as follows:
1) for each \(u_iu_l \in E(G)\) and for \(j,k=1,2,\ldots,p\), let \[\alpha((u_i, v_j)(u_l, v_k)) = p\beta(u_iu_l)-((j+k-1) \mod p),\]
2) for each \(u_i \in V(G)\) and \(v_jv_k \in E(H)\), let \[\alpha((u_i, v_j)(u_i, v_k)) = p\overline S(u_i, \beta)+\gamma(v_jv_k).\]
Clearly, \(\alpha\) is a proper edge-coloring of \(G[H]\) with colors \(1,2,\ldots,s'(G)p+s'(H)\), and the sum of colors on all the edges is \[\begin{split} \sum_{e\in E(G[H])}\alpha(e) &\le\sum_{1\le j, k\le p}\sum_{u_iu_l \in E(G)}p\beta(u_iu_l)\\ &-\sum_{u_iu_l\in E(G)}\sum_{1 \le j\le p}\sum_{1 \le k \le p}((j+k-1)\mod p) \\ &+ \sum_{u_i \in V(G)} \sum_{v_jv_k \in E(H)}ps'(G)+\sum_{u_i \in V(G)} \sum_{v_jv_k \in E(H)}\gamma(v_jv_k)\\ =&p^3\sum_{u_iu_l \in E(G)}\beta(u_iu_l) -\sum_{u_iu_l\in E(G)}\sum_{1 \le j\le p}\frac{p(p-1)}{2} \\ &+n\frac{rp}{2}ps'(G)+n\sum_{v_jv_k \in E(H)}\gamma(v_jv_k) \\ =&p^3\sum{'}(G)-\frac{p^2(p-1)m}{2}+\frac{nrp^2s'(G)}{2}+n\sum{'}(H). \end{split}\]
Note that if \(G\) and \(H\) admit a sequential coloring, we can choose \(\beta\) and \(\gamma\) as sequential colorings, and in that case, \(\alpha\) would also be a sequential, and therefore, a sum edge-coloring of \(G[H]\). ◻
In the following we first give an upper bound on the edge-chromatic sums of the Cartesian products of graphs. Next, we determine the edge-chromatic sums and edge-strengths of the Cartesian products of regular graphs and paths (cycles) with an even number of vertices. Finally, we determine the edge-chromatic sums and edge-strengths of grids, cylinders and tori.
Theorem 3.13. For any \((n, m)\)-graph \(G\) and \((p, q)\)-graph \(H\), we have \[\sum{'}(G \Box H) \le p\sum{'}(G)+n\sum{'}(H)+\min\{nqs'(G), pms'(H)\}.\]
Proof. It is sufficient to construct proper edge-colorings \(\alpha_1\) and \(\alpha_2\) of \(G \Box H\) for which the sums of colors on all edges are less than or equal to \(p\sum{'}(G)+n\sum{'}(H)+nqs'(G)\) and \(p\sum{'}(G)+n\sum{'}(H)+pms'(H)\) respectively. Let us denote the sum edge-coloring of \(G\) that uses colors \(1,2,\ldots,s'(G)\) by \(\beta\) and the sum edge-coloring of \(H\) that uses colors \(1, 2, \ldots, s'(H)\) by \(\gamma\). We now construct an edge-coloring \(\alpha_1\) of \(G\Box H\) as follows:
1) for each \(u_iu_l \in E(G)\) and \(v_j \in V(H)\), let \[\alpha_1((u_i, v_j)(u_l, v_j)) = \beta(u_iu_l),\]
2) for each \(u_i \in V(G)\) and \(v_jv_k \in E(H)\), let \[\alpha_1((u_i, v_j)(u_i, v_k)) = \gamma(v_jv_k)+\overline{S}(u_i, \beta).\]
Clearly, \(\alpha_1\) is a proper edge-coloring of \(G\Box H\) and the sum of all colors on the edges is \[\begin{split} \sum_{e \in E(G \Box H)}\alpha_1(e) =& \sum_{u_iu_l\in E(G)}\sum_{v_j \in V(H)}\beta(u_iu_l)\\ &+\sum_{u_i \in V(G)}\sum_{v_jv_k \in E(H)}(\gamma(v_jv_k)+\overline{S}(u_i, \beta)) \\ =&p\sum{'}(G)+n\sum{'}(H)+q\sum_{u_i\in V(G)}\overline{S}(u_i, \beta) \\ &\le p\sum{'}(G)+n\sum{'}(H)+qns'(G). \end{split}\]
Similarly, we construct an edge-coloring \(\alpha_2\) of \(G\Box H\) as follows:
1’) for each \(u_iu_l \in E(G)\) and \(v_j \in V(H)\), let \[\alpha_2((u_i, v_j)(u_l, v_j)) = \beta(u_iu_l)+\overline{S}(v_j, \gamma),\]
2’) for each \(u_i \in V(G)\) and \(v_jv_k \in E(H)\), let \[\alpha_2((u_i, v_j)(u_i, v_k)) = \gamma(v_jv_k).\]
Clearly, \(\alpha_2\) is a proper edge-coloring of \(G\Box H\) and the sum of all colors on the edges is less than or equal \(p\sum{'}(G)+n\sum{'}(H)+pms'(H)\). ◻
Note that in Theorem 3.13 if \(G\) and \(H\) admit a sequential coloring, we can choose \(\beta\) and \(\gamma\) as sequential colorings, and in that case \(\alpha_1\) (as well as \(\alpha_2\)) would be a sequential coloring of \(G \Box H\). This gives us the following:
Corollary 3.14. For any \((n, m)\)-graph \(G\) and \((p, q)\)-graph \(H\) that admit a sequential coloring, we have \(s'(G \Box H) = \Delta(G \Box H)\) and \[\sum{'}(G \Box H) = p\sum{'}(G)+n\sum{'}(H) +2mq.\]
We now consider graphs \(G \Box P_n\) and \(G \Box C_n\). Let \(V(G \Box P_n) =V(G\Box C_n)= \{(u, v_i) |~u \in V(G), 1 \le i \le n\}\) and \(E(G \Box P_n) = \{(u, v_i)(w, v_i) |~uw \in E(G), 1 \le i \le n\}\) \(\cup\) \(\{(u, v_i)(u, v_{i+1}) |~u \in V(G), 1 \le i \le n-1\}\), \(E(G \Box C_n) = E(G \Box P_n)\cup \{(u,v_n)(u,v_1)|~u\in V(G)\}\).
Theorem 3.15. (1) For any \(r\)-regular graph \(G\) and any \(n \; (n, r \in \mathbb{N})\), the edge-chromatic sum of the graph \(G \Box P_{2n}\) is determined as follows:
\[\sum{'}(G \Box P_{2n})=\frac{1}{2}|V(G)|(r+2)(nr+3n-2),\]
and the edge-strength of the graph \(G \Box P_{2n}\) is determined as follows: \[s'(G \Box P_{2n})=\begin{cases} r + 1, if \; n = 1,\\ r + 2, if \; n > 1. \end{cases}\]
(2) For any \(r\)-regular graph \(G\) and any \(n>1 \; (n, r \in \mathbb{N})\), the edge-chromatic sum of the graph \(G \Box C_{2n}\) is determined as follows:
\[\sum{'}(G \Box C_{2n})=\frac{1}{2}|V(G)|n(r+2)(r+3),\]
and the edge-strength of the graph \(G \Box C_{2n}\) is determined as follows: \[s'(G \Box C_{2n})=r + 2.\]
Proof. (1) By Theorem 2.6, we have \(s'(G) \le r + 1\). This implies that there exists a sum edge-coloring \(\alpha\) of \(G\) where for each vertex \(v \in V(G)\), there is exactly one missing color \(i \; (1 \le i \le r + 1)\) that does not belong to the spectrum of \(v\). Let us denote this color by \(mc_{\alpha}(v)\). Now we construct a proper edge-coloring \(\beta\) of \(G \Box P_{2n}\) in the following way:
a) for \(1 \le i \le 2n\), let \[\beta((u, v_i)(w, v_i)) = \alpha(uw).\]
b) for \(1 \le i \le n\), let \[\beta((u, v_{2i-1})(u, v_{2i}))=mc_{\alpha}(u).\]
c) for \(1 \le i \le n-1\), let \[\beta((u, v_{2i})(u, v_{2i+1}))=r+2.\]
This coloring \(\beta\) ensures the following upper bound on the edge-chromatic sum of \(G \Box P_{2n}\): \[\sum{'}(G \Box P_{2n})\le \frac{1}{2}|V(G)|(r+2)(nr+3n-2).\]
Now, by Lemma 2.1, \(\sum{'}(G \Box P_{2n}) \ge \frac{1}{2}|V(G)|(r+2)(nr+3n-2)\). Therefore, we obtain the exact values of \(s'(G \Box P_{2n})\) and \(\sum{'}(G \Box P_{2n})\).
(2) Similarly as in the previous proof, we construct a proper edge-coloring \(\gamma\) of \(G \Box C_{2n}\) in the following way:
a’) for each \(e\in E(G \Box P_{2n})\), let \(\gamma(e)=\beta(e)\),
b’) for each \(u \in V(G)\), let \(\gamma((u, v_{2n})(u, v_1))=r+2\).
This coloring \(\gamma\) ensures the following upper bound on the edge-chromatic sum of \(G \Box C_{2n}\): \[\sum{'}(G \Box C_{2n})\le \frac{1}{2}|V(G)|n(r+2)(r+3).\]
Now, again by Lemma 2.1, \(\sum{'}(G \Box C_{2n}) \ge \frac{1}{2}|V(G)|n(r+2)(r+3)\). Therefore, we obtain the exact values of \(s'(G \Box C_{2n})\) and \(\sum{'}(G \Box C_{2n})\). ◻
A similar strategy for the edge-coloring of the Cartesian products of regular graphs and simple paths (cycles) with an odd number of vertices gives a polynomial-time approximation algorithm, but is not always a sum edge-coloring. For example, \(\sum{'}(C_5 \Box P_3) = 58\), but the coloring we talk about results in a sum of \(59\).
In this section, we obtain the edge-strength and the edge-chromatic sum of the graphs \(P_n \Box P_m\), where \(n\) and \(m\) are natural numbers. We will consider only the non-trivial cases \(n > 1\) and \(m > 1\), since the rest are significantly easier to obtain.
Let \(V(P_n \Box P_m) = \{(u_i, v_j) |~1 \le i \le n, 1 \le j \le m\}\) and \(E(P_n \Box P_m) = \{(u_i, v_j)(u_{i+1}, v_j) |~1 \le i \le n-1, 1 \le j \le m\} \cup\) \(\{(u_i, v_j)(u_i, v_{j+1}) |~1 \le i \le n, 1 \le j \le m-1\}\).
Theorem 3.16. For any \(m,n\geq 2\) \((n, m \in \mathbb{N})\), we have \[\Sigma'(P_n \Box P_m)=\left\{ \begin{aligned} &5nm-4n-4m+2, & \text{if~} n \text{~or~} m \text{~is even},\\ &5nm-4n-4m+4, & \text{otherwise}, \end{aligned} \right.\] and \(s'(P_n \Box P_m) = \Delta(P_n \Box P_m)\).
Proof. First of all, let us note that since \(P_n \Box P_m\) is bipartite, by Theorems 2.4 and 2.5, we obtain \(s'(P_n \Box P_m)=\Delta(P_n \Box P_m)\).
Let us now consider the case where at least one of the paths has an even number of vertices.
Assume that \(G = P_{2n} \Box P_m\).
We show that \(\Sigma'(G) = 10nm-8n-4m+2\).
Note that simple paths with an even number of vertices admit a sequential coloring, such a coloring can be obtained by coloring the edges alternatively with colors \(1\) and \(2\). So in case \(m\) is even, Corollary 3.14 gives us the exact value of \(\sum{'}(G)\).
Let \(m\) be odd now. By Lemma 2.1, we get \(\Sigma'(G) \ge 10nm-8n-4m+2\). To show that this lower bound is achievable, we construct a proper edge-coloring \(\alpha\) with colors \(1,2,\ldots,\Delta(G)\) and with the required sum of colors.
We define an edge-coloring \(\alpha\) of \(G\) as follows:
1) for any \(1 \le i \le n\), let \[\alpha((u_{2i-1}, v_1)(u_{2i}, v_1)) = 2\text{ and }\alpha((u_{2i-1}, v_m)(u_{2i}, v_m)) = 1,\]
2) for any \(1 \le i \le n, 2 \le j \le m – 1\), let \[\alpha((u_{2i-1}, v_j)(u_{2i}, v_j)) = 3,\]
3) for any \(1 \le i \le n-1, j \in \{1, m\}\), let \[\alpha((u_{2i}, v_j)(u_{2i+1}, v_j)) = 3,\]
4) for any \(1 \le i \le n-1, 2 \le j \le m – 1\), let \[\alpha((u_{2i}, v_j)(u_{2i+1}, v_j)) = 4,\]
5) for any \(1 \le i \le 2n, 1 \le j \le \frac{m-1}{2}\), let \[\alpha((u_i, v_{2j-1})(u_i, v_{2j})) = 1\text{ and }\alpha((u_i, v_{2j})(u_i, v_{2j+1})) = 2.\]
Clearly, \(\alpha\) is a proper edge-coloring with \(1,2,\ldots,\Delta(G)\) colors and by summing up all the colors we obtain the desired result. Since the Cartesian product is commutative up to isomorphism, the case where the graph is \(P_n \Box P_{2m}\) is obtained similarly. Hence, it remains to consider the case where \(m\) and \(n\) are odd.
Let \(H = P_{2n+1} \Box P_{2m+1}\). We show that \(\sum{'}(H) = 20nm+2n+2m+1\).
Consider the set of vertices \(U = \{(u_i, v_j) | 1 \le i \le 2n+1, 1 \le j \le 2m+1, \; i + j \; \text{is odd}\}\) of \(H\). Clearly, \(H\) can be seen as a bipartite graph with parts \(U\) and \(V(H)\backslash U\). Obviously, \(\sum{'}(H) = \sum\limits_{v \in U}\sum\limits_{u \in N_H(v)}\beta(vu)\) for some sum edge-coloring \(\beta\). Similarly to the observations in the proof of Lemma 2.1, \(\sum{'}(H) = \sum\limits_{v \in U}\sum\limits_{u \in N_H(v)}\beta(vu) \ge \sum\limits_{v \in U}\frac{d_H(v)(d_H(v) + 1)}{2} = 20nm+2n+2m\). Moreover, the equality holds if and only if for each vertex \(v \in U\), \(\{\beta(vu) | ~u \in N_H(v)\} = \{1, 2,\ldots,d_H(v)\}\). However, in that case, since the number of vertices of degree \(4\) in \(U\) is \(2nm-n-m\), the number of edges colored with color \(4\) is also \(2nm-n-m\), while in \(V(H)\backslash U\), there are \(2nm-n-m+1\) vertices of degree \(4\), which means there is at least one vertex of degree \(4\) in \(V(H)\backslash U\) that is not incident to an edge colored with \(4\). Note that in this case \(\beta\) does not contain any color bigger than \(4\) either, so this vertex is incident to four edges which are colored using the colors \(1\), \(2\), and \(3\), which contradicts the assumption of \(\beta\) being a proper edge-coloring.
This means that \(\sum{'}(H) \ge 20nm+2n+2m+1\). Recalling that \(s'(H) = 4\), it only leaves us to construct an edge-coloring satisfying the requirements. Here is an example of such an edge-coloring \(\gamma\):
1) for any \(1 \le i \le n\), let \[\gamma((u_{2i-1}, v_1)(u_{2i}, v_1)) = 2,\]
2) for any \(1 \le i \le n, 2 \le j \le 2m + 1\), let \[\gamma((u_{2i-1}, v_j)(u_{2i}, v_j)) = 3,\]
3) for any \(1 \le i \le n – 1\), let \[\gamma((u_{2i}, v_1)(u_{2i+1}, v_1)) = 3\text{ and }\gamma((u_{2i}, v_{2m+1})(u_{2i+1}, v_{2m+1})) = 1,\]
4) for any \(1 \le i \le n-1, 2 \le j \le 2m,\) let \[\gamma((u_{2i}, v_j)(u_{2i+1}, v_j)) = 4,\]
5) let \[\gamma((u_{2n}, v_1)(u_{2n+1}, v_1)) = 1,\]
6) for any \(2 \le j \le 2m+1,\) let \[\gamma((u_{2n}, v_j)(u_{2n+1}, v_j)) = 2,\]
7) for any \(1 \le i \le 2n-1, 1 \le j \le m,\) let \[\gamma((u_i, v_{2j-1})(u_i, v_{2j})) = 1\text{ and }\gamma((u_i, v_{2j})(u_i, v_{2j+1})) = 2,\]
8) for any \(1 \le j \le m,\) let \[\gamma((u_{2n}, v_{2j-1})(u_{2n}, v_{2j})) = 4\text{ and }\gamma((u_{2n+1}, v_{2j-1})(u_{2n+1}, v_{2j})) = 3,\]
9) for any \(2n \le i \le 2n+1, 1 \le j \le m,\) let \[\gamma((u_i, v_{2j})(u_i, v_{2j+1})) = 1\].
Clearly, \(\gamma\) is a proper edge-coloring of \(H\) with colors \(1,2,3,4\) and \(\sum{'}(H,\gamma) =20nm+2n+2m+1\). ◻
In Figure 1, it can be seen the illustration of the sum edge-coloring of \(P_5 \Box P_7\) used in the proof of Theorem 3.16.
In this section, we obtain the edge-strength and the edge-chromatic sum of the graphs \(C_n \Box P_m\), where \(n \ge 3\) and \(m \ge 2\).
Let \(V(C_n \Box P_m) = \{(u_i, v_j) | 1 \le i \le n, 1 \le j \le m\}\) and \(E(C_n \Box P_m) = \{(u_i, v_j)(u_{i+1}, v_j) | 1 \le i \le n-1, 1 \le j \le m\} \cup \{(u_1, v_j)(u_n, v_j) | 1 \le j \le m\} \cup\) \(\{(u_i, v_j)(u_i, v_{j+1}) | 1 \le i \le n, 1 \le j \le m-1\}\).
Theorem 3.17. For any \(n\geq 3, m\geq 2\) \((n, m \in \mathbb{N})\), we have \[\Sigma'(C_n \Box P_m)=\left\{ \begin{aligned} &5nm-4n, & \text{if~} n \text{~or~} m \text{~is even},\\ &5nm-4n+3, & \text{otherwise}, \end{aligned} \right.\] and \(s'(C_n \Box P_m) = \Delta(C_n \Box P_m)\).
Proof. We distinguish three cases for the considered graph (we redefine the values of \(n\) and \(m\) for convenience and denote the graph by \(G\)):
1) \(G = C_n \Box P_{2m}\) for any \(n, m \in \mathbb{N}\) and \(n > 2\).
2) \(G = C_{2n} \Box P_{2m+1}\) for any \(n, m \in \mathbb{N}\) and \(n > 1\).
3) \(G = C_{2n+1} \Box P_{2m+1}\) for any \(n, m \in \mathbb{N}\).
Case 1. \(G = C_n \Box P_{2m}\) for any \(n, m \in \mathbb{N}\) and \(n > 2\).
We prove that \(\sum{'}(G) = 10nm-4n\) and \(s'(G) = \Delta(G)\).
In this case we apply the Theorem 3.15 and obtain the desired result.
Case 2. \(G = C_{2n} \Box P_{2m+1}\) for any \(n, m \in \mathbb{N}\) and \(n > 1\).
We prove that \(\sum{'}(G) = 20nm+2n\) and \(s'(G) = \Delta(G)\).
Since \(G\) is bipartite, by Theorems 2.4 and 2.5, we get that \(s'(G) = \Delta(G)\). By Lemma 2.1, we obtain that \(\sum{'}(G) \ge 20nm+2n\). Here we provide a proper edge-coloring \(\alpha\) that uses \(\Delta(G)\) colors and that satisfies the equality \(\sum{'}(G, \alpha) = 20nm + 2n\).
We define an edge-coloring \(\alpha\) of \(G\) as follows:
1) for any \(1 \le i \le n\), let \[\alpha((u_{2i-1}, v_1)(u_{2i}, v_1)) = 2\text{ and }\alpha((u_{2i-1}, v_{2m+1})(u_{2i}, v_{2m+1})) = 1,\]
2) for any \(1 \le i \le n, 2 \le j \le 2m\), let \[\alpha((u_{2i-1}, v_j)(u_{2i}, v_j)) = 3,\]
3) for any \(1 \le i \le n-1, j \in \{1, 2m+1\}\), let \[\alpha((u_{2i}, v_j)(u_{2i+1}, v_j)) = 3,\]
4) for any \(1 \le i \le n-1, 2 \le j \le 2m\), let \[\alpha((u_{2i}, v_j)(u_{2i+1}, v_j)) = 4,\]
5) for any \(1 \le i \le 2n, 1 \le j \le m\), let \[\alpha((u_i, v_{2j-1})(u_i, v_{2j})) = 1\text{ and }\alpha((u_i, v_{2j})(u_i, v_{2j+1})) = 2,\]
6) for any \(j \in \{1, 2m+1\}\), let \[\alpha((u_1, v_j)(u_{2n}, v_j)) = 3,\]
7) for any \(2 \le j \le 2m\), let \[\alpha((u_1, v_j)(u_{2n}, v_j)) = 4.\]
It is straightforward that \(\alpha\) is a proper edge-coloring of \(G\) with colors \(1,2,3,4\) and \(\sum{'}(G, \alpha) = 20nm + 2n\).
Case 3. \(G = C_{2n+1} \Box P_{2m+1}\) for any \(n, m \in \mathbb{N}\).
We prove that \(\sum{'}(G) = 20nm+2n+10m+4\) and \(s'(G) = \Delta(G)\).
Clearly, \(s'(G) \ge \Delta(G) = 4\), so putting \(k = 4\) in Lemma 2.2, we get \(\sum{'}(G) \ge 20nm+2n+10m+4\). Now we provide a proper edge-coloring \(\beta\) that uses \(\Delta(G) = 4\) colors and satisfies the following equality \(\sum{'}(G, \beta) = 20nm+2n+10m+4\).
We define an edge-coloring \(\beta\) of \(G\) as follows:
1) for any \(1 \le i \le n\), let \[\beta((u_{2i-1}, v_1)(u_{2i}, v_1)) = 2,\text{ and }\beta((u_{2i}, v_1)(u_{2i+1}, v_1)) = 3,\]
2) for any \(1 \le i \le n, 2 \le j \le 2m+1\), let \[\beta((u_{2i-1}, v_j)(u_{2i}, v_j)) = 3,\]
3) for any \(1 \le i \le n-1, 2 \le j \le 2m\), let \[\beta((u_{2i}, v_j)(u_{2i+1}, v_j)) = 4,\]
4) for any \(1 \le i \le n-1\), let \[\beta((u_{2i}, v_{2m+1})(u_{2i+1}, v_{2m+1})) = 1,\]
5) for any \(2 \le j \le 2m+1\), let \[\beta((u_{2n}, v_j)(u_{2n+1}, v_j)) = 2,\]
6) for any \(1 \le j \le 2m\), let \[\beta((u_1, v_j)(u_{2n+1}, v_j)) = 4,\]
7) let \[\beta((u_1, v_{2m+1})(u_{2n+1}, v_{2m+1})) = 1,\]
8) for any \(1 \le i \le 2n-1, 1 \le j \le m\), let \[\beta((u_i, v_{2j-1})(u_i, v_{2j})) = 1,\text{ and }\beta((u_i, v_{2j})(u_i, v_{2j+1})) = 2,\]
9) for any \(1 \le j \le m\), let \[\beta((u_{2n}, v_{2j-1})(u_{2n}, v_{2j})) = 4,\text{ and }\beta((u_{2n+1}, v_{2j-1})(u_{2n+1}, v_{2j})) = 1,\] \[\beta((u_{2n}, v_{2j})(u_{2n}, v_{2j+1})) = 1,\text{ and }\beta((u_{2n+1}, v_{2j})(u_{2n+1}, v_{2j+1})) = 3.\]
It is easy to verify that \(\beta\) is a proper edge-coloring of \(G\) with colors \(1,2,3,4\) and \(\sum{'}(G, \beta) = 20nm+2n+10m+4\). ◻
In Figure 2, it can be seen the illustration of the sum edge-coloring of \(C_5 \Box P_7\) used in the proof of Theorem 3.17.
Finally, we determine the edge-strength and the edge-chromatic sum of the graphs \(C_n \Box C_m\), where \(n,m\geq 3\). Let \(V(C_n \Box C_m) = \{(u_i, v_j) | 1 \le i \le n, 1 \le j \le m\}\) and \(E(C_n \Box C_m) = \{(u_i, v_j)(u_{i+1}, v_j) | 1 \le i \le n-1, 1 \le j \le m\} \cup \{(u_1, v_j)(u_n, v_j) | 1 \le j \le m\} \cup\) \(\{(u_i, v_j)(u_i, v_{j+1}) | 1 \le i \le n, 1 \le j \le m-1\} \cup \{(u_i, v_1)(u_i, v_m) | 1 \le i \le n\}\).
Theorem 3.18. For any \(n,m\geq 3\) \((n, m \in \mathbb{N})\), we have \[\Sigma'(C_n \Box C_m)=\left\{ \begin{aligned} &5nm, & \text{if~} n \text{~or~} m \text{~is even},\\ &5nm+5, & \text{otherwise}, \end{aligned} \right.\] and \[s'(C_n \Box C_m)=\left\{ \begin{aligned} &4, & \text{if~} n \text{~or~} m \text{~is even},\\ &5, & \text{otherwise.} \end{aligned} \right.\]
Proof. First of all, note that for regular graphs \(s'(G) =\chi'(G)\) [25]. If \(n\) or \(m\) is even, Theorem 2.3 ensures that \(\Delta(C_n\Box C_m)=4\).
In case both \(n\) and \(m\) are odd, the size of each color class in a proper edge-coloring is at most \(\left\lfloor\frac{|V(C_n\Box C_m)|}{2}\right\rfloor=\frac{nm-1}{2}\), and since there are \(2nm\) edges in total, \(4\) colors are not enough to color all the edges. Hence \[s'(C_n \Box C_m)=\left\{ \begin{aligned} &4, & \text{if~} n \text{~or~} m \text{~is even},\\ &5, & \text{otherwise.} \end{aligned} \right.\]
In case \(n\) or \(m\) is even, the Theorem 3.15 is applicable and gives us the desired result.
Let us redefine \(n\) and \(m\) and consider the graph \(G = C_{2n+1} \Box C_{2m+1}\) for any \(n, m \in \mathbb{N}\). It leaves us to prove that \(\sum{'}(G) = 20nm+10n+10m+10\).
Since \(s'(G) \ge 5\), putting \(k = 5\) in Lemma 2.2, we get \[\begin{aligned} \sum{'}(G) \ge& 5\left(2(2n+1)(2m+1) – 2\frac{(2n+1)(2m+1)-1}{2}\right)\\ =& 20nm+10n+10m+10. \end{aligned}\]
Now, to complete the proof, we show a proper edge-coloring \(\alpha\) with colors \(1,2,3,4,5\) such that \(\sum{'}(G, \alpha) = 20nm + 10n + 10m + 10\).
We define an edge-coloring \(\alpha\) of \(G\) as follows:
1) for any \(1 \le i \le n\), let \[\alpha((u_{2i-1}, v_1)(u_{2i}, v_1)) = 2\text{ and }\alpha((u_{2i}, v_1)(u_{2i+1}, v_1)) = 3,\]
2) for any \(1 \le i \le n, 2 \le j \le 2m+1\), let \[\alpha((u_{2i-1}, v_j)(u_{2i}, v_j)) = 3,\]
3) for any \(1 \le i \le n-1, 2 \le j \le 2m\), let \[\alpha((u_{2i}, v_j)(u_{2i+1}, v_j)) = 4,\]
4) for any \(1 \le i \le n-1\), let \[\alpha((u_{2i}, v_{2m+1})(u_{2i+1}, v_{2m+1})) = 1,\]
5) for any \(2 \le j \le 2m+1\), let \[\alpha((u_{2n}, v_j)(u_{2n+1}, v_j)) = 2,\]
6) \[\alpha((u_1, v_1)(u_{2n+1}, v_1)) = 5,\text{ and }\alpha((u_1, v_{2m+1})(u_{2n+1}, v_{2m+1})) = 1,\] \[\alpha((u_{2n}, v_1)(u_{2n}, v_{2m+1})) = 5,\text{ and }\alpha((u_{2n+1}, v_1)(u_{2n+1}, v_{2m+1})) = 4,\]
7) for any \(2 \le j \le 2m\), let \[\alpha((u_1, v_j)(u_{2n+1}, v_j)) = 4,\]
8) for any \(1 \le i \le 2n-1, 1 \le j \le m\), let \[\alpha((u_i, v_{2j-1})(u_i, v_{2j})) = 1\text{ and }\alpha((u_i, v_{2j})(u_i, v_{2j+1})) = 2,\]
9) for any \(1 \le j \le m\), let \[\alpha((u_{2n}, v_{2j-1})(u_{2n}, v_{2j})) = 4,\text{ and }\alpha((u_{2n+1}, v_{2j-1})(u_{2n+1}, v_{2j})) = 1,\] \[\alpha((u_{2n}, v_{2j})(u_{2n}, v_{2j+1})) = 1,\text{ and }\alpha((u_{2n+1}, v_{2j})(u_{2n+1}, v_{2j+1})) = 3,\]
10) for any \(1 \le i \le 2n – 1\), let \[\alpha((u_i, v_1)(u_i, v_{2m+1})) = 4.\]
It is easy to verify that \(\alpha\) is a proper edge-coloring of \(G\) with colors \(1,2,3,4,5\) and \(\sum{'}(G, \alpha) = 20nm + 10n + 10m + 10\). ◻
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.