Strong rainbow connection numbers of toroidal meshes
Yulong Wei Min Xu Kaishun Wang












=14cm =22cm = 0cm =1cm
= 0cm
footnote
thmTheorem[section]
defin[thm]Definition
prop[thm]Proposition
lem[thm]Lemma
fact[thm]Fact
cor[thm]Corollary
exampleExample
remarkRemark[section]
proProblem[section]
observation[thm]Observation






re 
eg 








GBKsong








 
 
 Strong rainbow connection numbers
of  toroidal meshes
    Yulong Wei[Corresponding author. E-mail address: yulong.wei@mail.bnu.edu.cn (Y. Wei), xum@bnu.edu.cn (M. Xu), wangks@bnu.edu.cn (K. Wang).]  Min Xu  Kaishun Wang

Sch. Math. Sci. & Lab. Math. Com. Sys., Beijing Normal University, Beijing, 100875,  China 
    
==================================================================================================================================================================================================================================================================






In 2011, Li et al. <cit.> obtained an upper bound of the strong rainbow connection number of an r-dimensional undirected toroidal mesh. In this paper, this bound is improved. As a result, we give a negative answer to their  problem.

Key words: toroidal mesh; (strong) rainbow path; (strong) rainbow connection number; Cayley graph.








§ INTRODUCTION


All graphs considered in this paper are finite, connected and simple. We refer to the
book <cit.> for graph theory notation and terminology not described here. Let Γ be a graph. Denote by V(Γ) and E(Γ) the vertex set and edge set of Γ, respectively. A sequence of distinct vertices is a path if any two consecutive vertices are adjacent. A path P:(v_1, v_2, …, v_k) is a cycle if v_1 is adjacent to v_k, denoted by C_k. The distance, d(u, v), between vertices u and v is equal to the length of a shortest path connecting u and v. The diameter of Γ, d(Γ), is the maximum distance between two vertices in Γ over all pairs of vertices.

Define a k-edge-coloring ζ: E(Γ)→{1,2,…,k}, k∈ℕ,
where adjacent edges may be colored the same. A path is rainbow if no two edges of
it are colored the same. A path from u to v is called a strong rainbow path if it's a rainbow path with length d(u, v).
If any two distinct vertices u and v of Γ are connected by a (strong) rainbow path, then Γ is called (strong) rainbow-connected under the coloring ζ, and ζ is called a (strong) rainbow k-coloring of Γ. The (strong) rainbow connection number of Γ, denoted by (src(Γ)) rc(Γ), is the minimum k for which there exists a (strong) rainbow k-coloring of Γ. Clearly, we have d(Γ)≤ rc(Γ)≤ src(Γ).

The (strong) rainbow connection number of a graph was first introduced by Chartrand et al. <cit.>. Ananth and Nasre <cit.> proved that, for every integer k≥3, deciding whether src(Γ)≤ k  is NP-hard even when Γ is bipartite.
(Strong) rainbow connection numbers of some special graphs have been studied in the literature, such as outerplanar graphs <cit.>, Cayley graphs <cit.>, line graphs <cit.>, power graphs <cit.>, undirected double-loop networks <cit.> and non-commuting graphs <cit.>.

The Cartesian product of two graphs Γ and Λ is the graph Γ□Λ whose vertex
set is the set {γλ | γ∈ V(Γ), λ∈ V(Λ)}, and two vertices γλ, γ' λ' are adjacent if λ=λ' and {γ,γ'}∈ E(Γ) or if γ=γ' and {λ,λ'}∈ E(Λ). The Cartesian product operation is commutative and associative, hence the Cartesian product of more factors is well-defined. The graph C_n_1□⋯□ C_n_r is an r-dimensional undirected toroidal mesh, where n_k≥2 for 1≤ k≤ r.

In 2011, Li et al. proved the following theorem and proposed an open problem.

<cit.>
Let C_n_k, n_k≥2, 1≤ k ≤ r be cycles. Then 
    ∑_1≤ k ≤ r⌊n_k/2⌋≤ rc(C_n_1□⋯□ C_n_r)≤ src(C_n_1□⋯□ C_n_r)≤∑_1≤ k ≤ r⌈n_k/2⌉.
 Moreover, if n_k is even for every 1≤ k ≤ r, then 
    rc(C_n_1□⋯□ C_n_r)= src(C_n_1□⋯□ C_n_r)=∑_1≤ k ≤ rn_k/2.


<cit.>
Given an Abelian group G and an inverse closed minimal generating set S⊆ G ∖ 1 of G, is it true that 
    src(C(G,S))= rc(C(G,S))=∑_a∈ S^*⌈|a|/2⌉?

where S^*⊆ S is a minimal generating set of G.


In this paper, we improve the upper bound of src(C_n_1□⋯□ C_n_r) in Theorem <ref>. Our main result is listed below.


Let C_n_k, n_k≥2, 1≤ k ≤ r be cycles. Then

    src(C_n_1□⋯□ C_n_r)≤{[   ⌈n_1+⋯+n_r-μ2⌉,         0≤μ≤⌊r2⌋;;                  ; ⌈n_1+⋯+n_r-r+μ2⌉,      ⌊r2⌋+1≤μ≤ r, ].

where μ is the number of even numbers among n_1, …, n_r.


Note that an r-dimensional undirected toroidal mesh is a Cayley graph. As a result, Theorem <ref> gives a negative answer to Problem <ref>.








§ PRELIMINARY RESULTS

In this section, we will introduce some useful results for the strong rainbow connection numbers of graphs.
<cit.>
For each integer n≥4, rc(C_n)= src(C_n)=⌈n/2⌉.


We make the following simple observation, which we will use repeatedly.

Let Γ and Λ be two connected graphs. Then 
    src(Γ) ≤ src(Γ□Λ)≤ src(Γ)+ src(Λ).





For each integer n≥3, src(C_n□ C_2)=⌈n+1/2⌉.

Write (0, 1, …, n-1) for C_n and (0, 1) for C_2. Since the diameter of C_n□ C_2 is ⌈n+1/2⌉, it suffices to show that src(C_n□ C_2)≤⌈n+1/2⌉. We only need to construct a strong rainbow ⌈n+1/2⌉-coloring. Now we divide our discussion into two cases.



Case 1   n=2k.

Define an edge-coloring f_1 of the graph C_2k□ C_2 by

    f_1(e)=
    {[                             k,                 if e={i0, i1};;                             i,  if e={ij, (i+1)j}, 0≤ i≤ k-1;;                           i-k, if e={ij, (i+1)j}, k≤ i≤ 2k-2;;                           k-1,            if e={(2k-1)j, 0j}. ].


For illustration, we give a strong rainbow 5-coloring of C_8□ C_2 in Figure <ref>.

Note that any path from u to v in Table <ref> is a strong rainbow path under the coloring f_1. It follows that f_1 is a strong rainbow (k+1)-coloring.





Case 2   n=2k+1.

Define an edge-coloring f_2 of the graph C_2k+1□ C_2 by

    f_2(e)=
    {[                               i,          if e={i0, i1}, 1≤ i≤ k;;                           i-k-1,       if e={i0, i1}, k+1≤ i≤ 2k;;                               k,                   if e={00, 01};;                               i,      if e={ij, (i+1)j}, 0≤ i≤ k;;                           i-k-1, if e={ij, (i+1)j}, k+1≤ i≤ 2k-1;;                             k-1,                if e={(2k)j, 0j}. ].


For illustration, we give a strong rainbow 4-coloring of C_7□ C_2 in Figure <ref>.

Note that any path from u to v in Table <ref> is a strong rainbow path under the coloring f_2. It follows that f_2 is a strong rainbow (k+1)-coloring. 



In the graph Γ□Λ, we write Γ y for Γ□{y}, where y∈ V(Λ).
The union of graphs Γ and Λ is the graph Γ∪Λ with vertex set V(Γ)∪ V(Λ) and edge set E(Γ)∪ E(Λ).

Let Γ be a connected graph. Then

    src(Γ□ C_n)≤⌈n-2/2⌉+ src(Γ□ C_2), n≥3.


Write (x_1, x_2, …, x_n) for C_n. Meanwhile, we use E[Γ x_i, Γ x_j] to denote the edge set between Γ x_i and Γ x_j.

By Observation <ref>, we have 
    src(Γ□ C_3)≤ src(C_3)+ src(Γ)=1+ src(Γ)≤ 1+ src(Γ□ C_2).
 Thus, (<ref>) holds for n=3. Now, we suppose that n≥4.

Let L_1 and L_2 be induced subgraphs of Γ□ C_n  whose vertex sets are V(Γ x_1)∪ V(Γ x_n) and V(Γ x_⌊n/2⌋)∪ V(Γ x_⌊n/2⌋+1) respectively. Then each L_i is isomorphic to Γ□ C_2. Let S_0={1, …, ⌈n-2/2⌉}. Suppose that f_1: E(Γ)→ S_1 is a strong rainbow src(Γ)-coloring of Γ, and f_2, i: E(L_i)→ S_2 is a strong rainbow src(Γ□ C_2)-coloring of L_i for 1≤ i≤2, where S_0∩ S_2=∅. By Observation <ref>, we may assume that S_1⊆ S_2.
Define an edge-coloring f_3: E(Γ□ C_n)→ S_0∪ S_2 by

    f_3(e)=
    {[                                                     i,                 if e∈ E[Γ x_i, Γ x_i+1], 1≤ i≤⌊n/2⌋-1;;                                               i-⌊n/2⌋,              if e∈ E[Γ x_i, Γ x_i+1], ⌊n/2⌋+1≤ i≤ n-1;;                                             f_2,i(e) ,                               if e∈ E(L_i) for 1≤ i≤2;;                                       f_1({y_1, y_2}), if e={y_1x_i, y_2x_i}∈ E[Γ x_i, Γ x_i], n≥ 5 and i∈ I, ].

where I={2, 3, …, ⌊n/2⌋-1, ⌊n/2⌋+2, …, ⌊n/2⌋+3, …, n-1}.  For illustration of f_3, see Figure <ref>.


Pick any two distinct vertices u and v of Γ□ C_n. Write u=y_1x_i and v=y_2x_j. Without loss of generality, we may assume that i≤ j.  We only need to show that there exists a strong rainbow path from u to v under f_3.
 If i=j, the desired result is obvious. Assume that i≠ j. We divide our discussion into three cases.

Case 1   1≤ j-i≤⌊n/2⌋, and 2≤ j≤⌊n/2⌋ or ⌊n/2⌋+1≤ i≤ n-1.

Pick a strong rainbow path P_1 from y_1x_j to v in Γ x_j. Then 
    (u=y_1x_i, y_1x_i+1, …, y_1x_j)∪ P_1
 is a desired strong rainbow path.

Case 2   1≤ j-i≤⌊n/2⌋, j≥⌊n/2⌋+1 and i≤⌊n/2⌋.

Pick a strong rainbow path P_2 from y_1x_⌊n/2⌋ to y_2x_⌊n/2⌋+1 in L_2. Then 
    (u=y_1x_i, y_1x_i+1, …, y_1x_⌊n/2⌋) ∪ P_2 ∪(y_2x_⌊n/2⌋+1, y_2x_⌊n/2⌋+2, …, y_2x_j=v)
 is a desired strong rainbow path.

Case 3   j-i≥⌊n/2⌋+1.

Pick a strong rainbow path P_3 from y_1x_1 to y_2x_n in L_1. Then 
    (u=y_1x_i, y_1x_i-1, …, y_1x_1)∪ P_3 ∪(y_2x_n, y_2x_n-1,…, y_2x_j+1, y_2x_j=v)
 is a desired strong rainbow path.

As mentioned above, we obtain the desired result. 



§ PROOF OF THEOREM <REF>


Let C_n_k, n_k≥2, 1≤ k ≤ r be cycles. Then

    src(C_n_1□⋯□ C_n_r)≤⌈n_1+⋯+n_r/2⌉.


Without loss of generality, we may assume that n_1≥ n_2≥⋯≥ n_r. We distinguish two cases.



Case 1   n_r≥3.

We prove this proposition by induction on r. If r=1, (<ref>) is derived from Lemma <ref>. Suppose r=2. If n_2 is even, then by Lemma <ref> and Observation <ref>, (<ref>) holds.
If n_2 is odd, then by Proposition <ref> and Lemma <ref>, we have

    src(C_n_1□ C_n_2)   ≤   ⌈n_2-2/2⌉+ src(C_n_1□ C_2)=⌈n_1+n_2/2⌉.


Now, Suppose r≥3.

If each n_i is odd, then

    src(C_n_1□⋯□ C_n_r-1□ C_n_r)
       ≤   ⌈n_r-2/2⌉+ src((C_n_1□⋯□ C_n_r-2)□ (C_n_r-1□ C_2))  ( by Proposition <ref>)
       ≤   ⌈n_r-2/2⌉+ src(C_n_1□⋯□ C_n_r-2)+ src(C_n_r-1□ C_2)  ( by Observation <ref>)
       ≤   ⌈n_r-2/2⌉+⌈n_1+
    ⋯+n_r-2/2⌉+⌈n_r-1+1/2⌉  ( by induction hypothesis  and Lemma <ref>)
       =   ⌈n_1+⋯+n_r/2⌉.


If n_i is even for some i, then

    src(C_n_1□⋯□ C_n_r)
       ≤    src(C_n_1□⋯□ C_n_i-1□ C_n_i+1□⋯□ C_n_r)+ src(C_n_i)  ( by Observation <ref>)
       ≤   ⌈n_1+⋯+n_i-1+n_i+1+⋯+n_r/2⌉+⌈n_i/2⌉  ( by induction hypothesis)
       =   ⌈n_1+⋯+n_r/2⌉.




Case 2   n_r=2.

Suppose s is the minimum positive integer such that n_s=2.


Case 2.1   s=1.
By Observation <ref>, (<ref>) is obtained.



Case 2.2   s≥ 2.
In this case, we have

    src(C_n_1□⋯□ C_n_r)
       ≤    src(C_n_1□⋯□ C_n_s-1)+ src(C_2□⋯□ C_2)  ( by Observation <ref>)
       ≤   ⌈n_1+⋯+n_s-1/2⌉+r-s+1  ( by Case 1)
       =   ⌈n_1+⋯+n_r/2⌉.


Combining Case 1 and Case 2, we obtain the desired result. 



Proof of Theorem <ref>: 
If r=1, (<ref>) is obvious. Now, suppose r≥ 2. We divide our discussion into three cases.


Case 1   r=2.


If n_1=n_2=2, Observation <ref> implies that (<ref>) holds. Now suppose n_j≥ 3, for some j. Without loss of generality, we may assume that n_1≥ 3. By Proposition <ref> and Lemma <ref>, we have

    src(C_n_1□ C_n_2)≤⌈n_2-2/2⌉+ src(C_n_1□ C_2)
    =⌈n_2-2/2⌉+⌈n_1+1/2⌉.


If μ=1 and n_1 is even, then

    src(C_n_1□ C_n_2)= src(C_n_2□ C_n_1)≤⌈n_1-2/2⌉+ src(C_n_2□ C_2)=⌈n_1+n_2-1/2⌉.
 Otherwise, (<ref>) implies (<ref>).



Case 2   r=3.



If μ=0 or μ=3, (<ref>) holds by Proposition <ref>. Now suppose μ=1 or μ=2. Without loss of generality, we assume that n_1 is even and n_3 is odd. By Observation <ref>, Lemma <ref> and Case 1, we have

    src(C_n_1□ C_n_2□ C_n_3)≤ src(C_n_1)+ src(C_n_2□ C_n_3)
    ≤⌈n_1+n_2+n_3-1/2⌉.


Case 3   r≥4.


If μ=0 or μ=r, Proposition <ref> implies (<ref>).
In the following, we assume that n_1, …, n_μ are even and n_μ+1, …, n_r are odd.

Case 3.1   1≤μ≤⌊r/2⌋-1.

    src(C_n_1□⋯□ C_n_r)
       ≤    src(C_n_2μ+1□⋯□ C_n_r)+∑_1≤ s≤μ, s+t=2μ+1 src(C_n_s□ C_n_t)  ( by Observation <ref>)
       ≤   ⌈n_2μ+1+⋯+n_r/2⌉+∑_1≤ s≤μ, s+t=2μ+1n_s+n_t-1/2  ( by Proposition <ref>  and Case 1)
       =   ⌈n_1+⋯+n_r-μ/2⌉.


Case 3.2   μ=⌊r/2⌋.

    src(C_n_1□⋯□ C_n_r)
       ≤   1/2(1+(-1)^r+1) src(C_n_r)+∑_1≤ s≤μ, s+t=2μ+1 src(C_n_s□ C_n_t)  ( by Observation <ref>)
       ≤   1/2(1+(-1)^r+1)⌈n_r/2⌉+∑_1≤ s≤μ, s+t=2μ+1n_s+n_t-1/2  ( by Proposition <ref>  and Case 1)
       =   ⌈n_1+⋯+n_r-μ/2⌉.


Case 3.3   ⌊r/2⌋+1≤μ≤ r-1.

    src(C_n_1□⋯□ C_n_r)
       ≤    src(C_n_1□⋯□ C_2μ-r)+∑_μ+1≤ t≤ r, s+t=2μ+1 src(C_n_s□ C_n_t)  ( by Observation <ref>)
       ≤   ⌈n_1+⋯+n_2μ-r/2⌉+∑_μ+1≤ t≤ r, s+t=2μ+1n_s+n_t-1/2  ( by Proposition <ref>  and Case 1)
       =   ⌈n_1+⋯+n_r-r+μ/2⌉.


As mentioned above, we obtain the desired result. 




§ ACKNOWLEDGEMENT

M. Xu's research is supported by the National Natural Science Foundation of China (11571044, 61373021).
K. Wang's research is supported by the National Natural Science Foundation of China (11671043, 11371204).


99

AN  P. Ananth, M. Nasre, New hardness results in rainbow connectivity, arXiv:1104.2074v1 [cs.CC], 2011.

BMG J.A. Bondy, U.S.R. Murty, Graph Theory, GTM 244, Springer, 2008.



CJMZ G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem., 133 (1) (2008), 85–98.

DXX X. Deng, K. Xiang and B. Wu, Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs, Appl. Math. Lett., 25 (2012), 237–244.



LLL H. Li, X. Li and S. Liu, The (strong) rainbow connection numbers of Cayley graphs on Abelian groups, Comput. Math. Appl.,  62 (11) (2011), 4082–4088.

LSue X. Li and Y. Sun, Upper bounds for the rainbow connection numbers of line graphs, Graphs Combin., 28 (2)  (2012), 251–263.

MFW X. Ma, M. Feng and K. Wang, The rainbow connection number of the power graph of a finite group, Graphs Combin., 32 (4) (2016), 1495–1504.

ML  Y.B. Ma and Z.P. Lu, Rainbow connection numbers of Cayley graphs, J. Comb. Optim., http://dx.doi.org/10.1007/s10878-016-0052-6.

SY Y. Sun, Rainbow connection numbers for undirected double-loop networks, Advances in global optimization, 109–116, Springer Proc. Math. Stat., 95, Springer, Cham, 2015.

WMW Y. Wei, X. Ma and K. Wang, Rainbow connectivity of the non-commuting graph of a finite group, J. Algebra Appl., 15 (2016), 1650127, 8pp.








