Rainbow connection number of generalized composition

Abstract

Let $G$ be a connected graph with $V\left(G\right)=\{v_1,\dots ,v_n\}$. The rainbow connection number $rc\left(G\right)$ is the smallest $k$ for which there is a map $\gamma :E\left(G\right)\to \{1,\dots ,k\}$ such that any two vertices can be connected by a path whose edge colors are all distinct. The generalized composition $G[H_1,\dots ,H_n]$ is obtained by replacing each $v_i$ with the graph $H_i$. We prove $rc\left(G[H_1,\dots ,H_n]\right)=diam\left(G\right)$ if each $H_i$ has at least $diam\left(G\right)\ge 4$ vertices, improving known upper bounds of Basavaraju et al. and Gologranc et al. (2014). We prove the same result when $diam\left(G\right)=3$ but with some additional conditions. When $diam\left(G\right)=2$, we show that the largest possible value of $rc\left(G[H_1,\dots ,H_n]\right)$ is related to whether every vertex of $G$ is contained in a triangle or not.

Keywords:

• Composition
• Lexicographic product
• Rainbow connection

1 Introduction

In 2008 Chartrand et al. [1] introduced new concepts that use edge-coloring to strengthen the connectedness property of a graph. An edge-coloring on a graph $G$ is a map $E\left(G\right)\to \{1,\dots ,k\}$ (also called “$k$-coloring”). A rainbow path is a path whose edge colors are all distinct. A rainbow coloring is an edge-coloring in which any two vertices can be connected by a rainbow path. The rainbow connection number $rc\left(G\right)$ is the smallest $k$ for which $G$ has a rainbow $k$-coloring. A strong rainbow coloring is an edge-coloring in which any two vertices can be connected by a rainbow geodesic. The strong rainbow connection number $src\left(G\right)$ is the smallest $k$ for which $G$ has a strong rainbow $k$-coloring.

We have [1] (1) $$diam\left(G\right)\le rc\left(G\right)\le src\left(G\right)\le \left|E\left(G\right)\right|.$$(1)

The reader is referred to [2] for a detailed survey. It is known that computing rc and src is NP-hard [3]. Many studies have focused on special classes of graphs or graph operations, such as Cartesian product, strong product, lexicographic product (see [4] and [5]), and graph join (see [6]).

We study generalized composition, which can be thought of as “blowing-up” vertices into individual graphs. Let $V\left(G\right)=\{v_1,\dots ,v_n\}$, and $H_1,\dots ,H_n$ be any graphs. The generalized composition $G[H_1,\dots ,H_n]$ is obtained by replacing each $v_i$ with $H_i$ and adding a new edge between every vertex of $H_i$ and every vertex of $H_j$ whenever $v_i{v}_j\in E\left(G\right)$. We call this operation as $G$-composition. See Fig. 1.

Fig. 1 More examples, $P_3[P_2,C_3,K_1]$ (left) and $K_{1,3}[2K_1,P_3,K_1,P_2]$ (right).

Examples.

$P_2[H_1,H_2]=H_1+H_2$ is the usual graph join, and a $P_n$-composition is known as a sequential join. The special case $G\circ H=G[H,H,\dots ,H]$ is known as composition or lexicographic product.

We always assume that $G$ is non-trivial and connected. If $G[H_1,\dots ,H_n]$ is not a complete graph, then its diameter is $max\{2,diam\left(G\right)\}$. So (2) $$rc\left(G[H_1,\dots ,H_n]\right)\ge diam\left(G\right).$$(2) If each $H_i$ has at least $diam\left(G\right)\ge 4$ vertices, we show that (2) becomes an equality. When $H_1=\cdots =H_n$, this improves the results of Basavaraju et al. [4] $(rc(G\circ H)\le 2rad\left(G\right))$ and Gologranc et al. [5] $(rc(G\circ H)\le 2diam\left(G\right)+1)$.

If $diam\left(G\right)\le 3$, the bound (2) can be strict. However, we show that equality occurs when $diam\left(G\right)=3$ and some conditions are met (either each $H_i$ has at least one edge, or $G$ has the property that there is a 3-walk between every pair $x,y\in V\left(G\right)$ possibly with $x=y$). When $diam\left(G\right)=2$, we show that the largest possible value of $rc\left(G[H_1,\dots ,H_n]\right)$ determines whether every vertex of $G$ is contained in a triangle or not.

2 Results

2.1 A preliminary bound

Let $Q\subseteq V\left(G\right)$. Its common neighborhood $CN\left(Q\right)$ is the intersection of $N\left(v\right)=\{w:vw\in E\left(G\right)\}$ over all $v\in Q$. A set of vertices is independent if any two are non-adjacent, or co-neighboring if $N\left(v\right)=N\left(w\right)\ne \varnothing$ for all $v,w\in Q$.

Lemma 1

Let $Q\subseteq V\left(G\right)$ be a co-neighboring set. Then

(1)	$src\left(G\right)\ge {\left|Q\right|}^{\frac{1}{\left|CN\left(Q\right)\right|}}$.
(2)	If moreover $CN\left(Q\right)$ is independent, then $rc\left(G\right)\ge min\left\{4,{\left|Q\right|}^{\frac{1}{\left|CN\left(Q\right)\right|}}\right\}$.

Proof

This is based on an idea in [1]. Let $CN\left(Q\right)=\{t_1,\dots ,t_b\}$. Given a $k$-coloring $\gamma$ on $G$, define the color code of $v\in Q$ with respect to $CN\left(Q\right)$ as (3) $$code\left(v\right)=(\gamma \left(v{t}_1\right),\dots ,\gamma \left(v{t}_b\right)).$$(3) Note that there are at most $k^b$ distinct codes.

Claim

There is a rainbow geodesic between $v,w\in Q$ if and only if $code\left(v\right)\ne code\left(w\right)$.

In fact, any geodesic between $v$ and $w$ has the form $v-t-w$ with $t\in CN\left(Q\right)$, which is rainbow if and only if $\gamma \left(vt\right)\ne \gamma \left(wt\right)$. Now we prove the lower bounds.

(1) Let $k=⌈\sqrt[b]{\left|Q\right|}⌉-1$. Suppose $src\left(G\right)\le k$, so there is a strong rainbow $k$-coloring on $G$. Since $k^b<\left|Q\right|$, there are $v,w\in Q$ with the same code. By the claim, there are no rainbow geodesics between them, a contradiction.

(2) Let $k=min\{3,⌈\sqrt[b]{\left|Q\right|}⌉-1\}$. Suppose $rc\left(G\right)\le k$, so there is a rainbow $k$-coloring on $G$. Since $k^b<\left|Q\right|$, there are $v,w\in Q$ with the same code. Let $L:v-x-\cdots -y-w$ be a rainbow geodesic between $v$ and $w$. Then $x,y\in CN\left(Q\right)$, since $Q$ is co-neighboring. By the claim, $L$ is not a rainbow geodesic. So $x\ne y$. Since $CN\left(Q\right)$ is independent, $d_G(x,y)\ge 2$. The length of $L$ is at least $2+d_G(x,y)\ge 4$, contradicting $k\le 3$. □

Below is the reason we only study the rc of $G$-compositions, not the src.

Corollary 1

The src of $G$-compositions cannot be bounded above in terms of $G$ alone.

Proof

Let $k,c\in \mathbb{N}$. Replace some $v\in V\left(G\right)$ with $m{K}_1$ such that $m>c^{kdeg\left(v\right)}$, and replace any other vertex with $k{K}_1$, to get a $G$-composition graph $A$. The set $Q=V\left(m{K}_1\right)$ is co-neighboring and $\left|CN\left(Q\right)\right|=kdeg\left(v\right)$, so by Lemma 1 (1) we have $src\left(A\right)\ge {\left|Q\right|}^{\frac{1}{\left|CN\left(Q\right)\right|}}>c$. □

2.2 Diameter at least four

Theorem 1

Let $diam\left(G\right)\ge 4$ and $n=\left|V\left(G\right)\right|$. If each $H_i$ has at least $diam\left(G\right)$ vertices, then $rc\left(G[H_1,\dots ,H_n]\right)=diam\left(G\right)$.

We prove the upper bound separately for later use.

Lemma 2

If each $H_i$ has at least $max\{4,diam\left(G\right)\}$ vertices, then (4) $$rc\left(G[H_1,\dots ,H_n]\right)\le max\{4,diam\left(G\right)\}.$$(4)

Proof

Let $A=G[H_1,\dots ,H_n]$ and $V\left(H_i\right)=\left\{(i,j)\right|1\le j\le n_i\}$. We will construct a rainbow $u$-coloring on $A$, where $u=max\{4,diam\left(G\right)\}$. Define a map $\gamma :E\left(A\right)\to \{0,1,\dots ,u-1\}$ arbitrarily on each $E\left(H_i\right)$, and put (5) $$\gamma \left((i,j)(i^{\prime },j^{\prime })\right)=j+j^{\prime }(modu)$$(5) for all $i,i^{\prime }$ adjacent in $G$. We show that $\gamma$ is a rainbow coloring.

Let $x=(i,j)$, $y=(i^{\prime },j^{\prime })$ with $i,i^{\prime }$ non-adjacent in $G$. We will find a rainbow path between $x$ and $y$.

Case 1: $d_G(i,i^{\prime })=0$ or $2$.

Choose a common neighbor $i_1$ of $i,i^{\prime }$. If $j\equiv j^{\prime }(modu)$, then the path $(i,j)\stackrel{2j}{-}(i_1,j)\stackrel{2j+1}{-}(i,j+1)\stackrel{2j+3}{-}(i_1,j+2)\stackrel{2j+2}{-}(i^{\prime },j^{\prime })$ is rainbow. Otherwise, the path $(i,j)\stackrel{2j}{-}(i_1,j)\stackrel{j+j^{\prime }}{-}(i^{\prime },j^{\prime })$ is rainbow.

Case 2: $d_G(i,i^{\prime })=2m+1\ge 3$.

Choose a path $i-i_1-\cdots -i_{2m}-i^{\prime }$ in $G$. Define the numbers $j_1,j_2,\dots ,j_{2m}\in \{0,1,\dots ,u-1\}$ as $j_{2k-1}=j+j^{\prime }+m-k+1(modu)$ and $j_{2k}=j-k(modu)$, for each $k\in \{1,2,\dots ,m\}$. Thus (6) $$j_1=j+j^{\prime }+m,j_3=j+j^{\prime }+m-1,\dots ,j_{2m-1}=j+j^{\prime }+1$$(6) and (7) $$j_2=j-1,j_4=j-2,\dots ,j_{2m}=j-m.$$(7) Consider the following path, (8) $$L:(i,j)-(i_1,j_1)-(i_2,j_2)-\cdots (i_{2m},j_{2m})-(i^{\prime },j^{\prime }).$$(8) The color sequence of this path is (9) $$2j+j^{\prime }+m,2j+j^{\prime }+m-1,2j+j^{\prime }+m-2,\dots ,2j+j^{\prime }-m.$$(9) The numbers above are $2m+1$ consecutive integers in decreasing order. Since $2m+1\le u$, these numbers are all different modulo $u$. So $L$ is a rainbow path.

Case 3: $d_G(i,i^{\prime })=2m\ge 4$.

Use the path in Case 2 after deleting the penultimate vertex. □

2.3 Diameter three

The conclusion of Theorem 1 can fail when $diam\left(G\right)=3$ even if we control the number of vertices in each $H_i$. Below is a class of such examples.

Theorem 2

If $diam\left(G\right)\le 4$ and some vertex of $G$ is not contained in any triangle, then for any fixed $k\ge 4$ we have (10) $$\underset{k}{max}rc\left(G[H_1,\dots ,H_n]\right)=4$$(10) where the maximum is taken over all possible graphs $H_1,\dots ,H_n$ such that each $H_i$ has at least $k$ vertices.

Proof

By Lemma 2, the maximum is at most 4. To build a tight example, choose some $v\in V\left(G\right)$ not in any triangle. Replace $v$ with $m{K}_1$ where $m>3^{kdeg\left(v\right)}$, and every other vertex with $k{K}_1$ to form a $G$-composition graph $A$. Then $Q=V\left(m{K}_1\right)$ is co-neighboring and $CN\left(Q\right)$ is independent (otherwise $v$ would be in a triangle) so $rc\left(A\right)\ge min\left\{{\left|Q\right|}^{\frac{1}{\left|CN\left(Q\right)\right|}},4\right\}>3$ by Lemma 1. □

If some additional conditions are met, we do have an exact result.

Theorem 3

Let $G$ be a connected graph with $diam\left(G\right)=3$, and let $H_1,\dots ,H_n$ be arbitrary graphs with at least three vertices each. Suppose that one of the following holds,

(1)	each $H_i$ has at least one edge, or
(2)	$G$ contains a 3-walk between every pair $x,y\in V\left(G\right)$ (possibly with $x=y$).

Then $rc\left(G[H_1,\dots ,H_n]\right)=3$.

Proof

Let $V\left(G\right)=\{1,\dots ,n\}$ and $A=G[H_1,\dots ,H_n]$.

First, assume that (1) holds. We will construct a rainbow 3-coloring on $A$. We start with the following procedure.

(1)	For each $i\in \{1,\dots ,n\}$, choose a spanning forest $F_i$ for $H_i$.
(2)	Choose a bipartition $V\left(F_i\right)=V_i\cup W_i$ so that $\left|V_i\right|\ge 1$ and $\left|W_i\right|\ge 2$. This is possible since we assumed $\left|V\left(H_i\right)\right|\ge 3$.
(3)	Put all isolated vertices of $H_i$ (if any) in $W_i$.
(4)	Choose a non-isolated vertex of $H_i$ (which exists, because we assumed $E\left(H_i\right)\ne \varnothing$), and put it in $W_i$. Denote that vertex by $s_i$.

Now we define a map $\gamma :E\left(A\right)\to \{0,1,2\}$ as follows.

(1)	$\gamma \left(e\right)=0$ for each $e\in E\left(H_i\right)$ or $e=xy$ with $x\in V_i\cup \left\{s_i\right\}$ and $y\in V_j$.
(2)	$\gamma \left(xy\right)=1$ if $x\in W_i\setminus \left\{s_i\right\}$ and $y\in V_j$.
(3)	$\gamma \left(xy\right)=2$ if $x\in W_i$ and $y\in W_j$.

We show that $\gamma$ is a rainbow coloring. Let $x,y\in V\left(A\right)$ be non-adjacent. Then $x\in V\left(H_i\right)$ and $y\in V\left(H_j\right)$ for some non-adjacent $i,j$ in $G$.

Case 1: $d_G(i,j)=0$ or $d_G(i,j)=2$.

Choose a walk $i-i_1-j$ in $G$.

Subcase 1.1: $x\in V_i$ and $y\in V_j$.

Choose $w_1\in W_i\cap N\left(x\right)$ and $w_2\in W_{i_1}\setminus \left\{s_{i_1}\right\}$. Then $x\stackrel{0}{-}{w}_1\stackrel{2}{-}{w}_2\stackrel{1}{-}y$ is rainbow.

Subcase 1.2: $x\in V_i$ and $y\in W_j$.

The path $x\stackrel{0}{-}{s}_{i_1}\stackrel{2}{-}y$ is rainbow.

Subcase 1.3: $x\in W_i$ is not isolated in $H_i$ and $y\in W_j$.

Choose $v\in V_i\cap N\left(x\right)$ and $w\in W_{i_1}\setminus \left\{s_{i_1}\right\}$. Then $x\stackrel{0}{-}v\stackrel{1}{-}w\stackrel{2}{-}y$ is rainbow.

Subcase 1.4: $x\in W_i$ is isolated in $H_i$ and $y\in W_j$ is isolated in $H_j$.

Choose adjacent $v\in V_{i_1},w\in W_{i_1}$. The path $x\stackrel{1}{-}v\stackrel{0}{-}w\stackrel{2}{-}y$ is rainbow.

Case 2: $d_G(i,j)\ge 3$.

Choose a path $i-i_1-i_2-j$ in $G$.

Subcase 2.1: $x\in V_i$ and $y\in V_j$.

Choose $w\in W_{i_2}\setminus \left\{s_{i_2}\right\}$. Then the path $x\stackrel{0}{-}{s}_{i_1}\stackrel{2}{-}w\stackrel{1}{-}y$ is rainbow.

Subcase 2.2: $x\in V_i$ and $y\in W_j$.

Choose $v\in V_{i_1}$ and $w\in W_{i_2}\setminus \left\{s_{i_2}\right\}$. Then $x\stackrel{0}{-}v\stackrel{1}{-}w\stackrel{2}{-}y$ is rainbow.

Subcase 2.3: $x\in W_i\setminus \left\{s_i\right\}$ and $y\in W_j$.

Choose any $v\in V_{i_1}$. Then $x\stackrel{1}{-}v\stackrel{0}{-}{s}_{i_2}\stackrel{2}{-}y$ is rainbow.

Subcase 2.4: $x=s_i$ and $y\in W_j$.

Choose $v\in V_{i_1}$ and $w\in W_{i_2}\setminus \left\{s_{i_2}\right\}$. Then $x\stackrel{0}{-}v\stackrel{1}{-}w\stackrel{2}{-}y$ is rainbow.

This proves that if (1) holds, then $rc\left(G[H_1,\dots ,H_n]\right)=3$. If (2) holds, we are done by the next lemma which we prove separately for later use. □

Lemma 3

If $G$ contains a 3-walk between any $x,y\in V\left(G\right)$ (possibly with $x=y$), and each $H_i$ has at least 3 vertices, then $rc\left(G[H_1,\dots ,H_n]\right)\le 3$.

Proof

We will construct a rainbow 3-coloring on $A=G[H_1,\dots ,H_n]$. Let $V\left(H_i\right)=\left\{(i,j)\right|1\le j\le n_i\}$. Define a map $\gamma :E\left(A\right)\to \{0,1,2\}$ arbitrarily on each $E\left(H_i\right)$, and put (11) $$\gamma \left((i,j)(i^{\prime },j^{\prime })\right)=j+j^{\prime }(mod3)$$(11) for all $i,i^{\prime }$ adjacent in $G$. We prove that $\gamma$ is a rainbow coloring.

Let $x,y\in V\left(A\right)$ be non-adjacent, say $x=(i,j)$ and $y=(i^{\prime },j^{\prime })$ with $i,i^{\prime }$ non-adjacent in $G$. Choose any walk $i-i_1-i_2-i^{\prime }$ in $G$. We use this walk to find a rainbow path between $x$ and $y$.

If $j\equiv j^{\prime }(mod3)$, use $(i,j)\stackrel{2j+1}{-}(i_1,j+1)\stackrel{2j+3}{-}(i_2,j+2)\stackrel{2j+2}{-}(i^{\prime },j^{\prime })$. If $j\not\equiv j^{\prime }(mod3)$, use $(i,j)\stackrel{2j}{-}(i_1,j)\stackrel{j+j^{\prime }}{-}(i_2,j^{\prime })\stackrel{2j^{\prime }}{-}(i^{\prime },j^{\prime })$ as a rainbow path. □

2.4 Diameter two

The rc of a graph can sometimes determine the structure of that graph. For instance, $rc\left(G\right)=1$ if and only if $G$ is a complete graph, while $rc\left(G\right)=\left|E\left(G\right)\right|$ if and only if $G$ is a tree (see [1]). Below, we show that if $diam\left(G\right)=2$ then the largest possible value of $rc\left(G[H_1,\dots ,H_n]\right)$ determines whether every vertex of $G$ is contained in a triangle or not.

Theorem 4

If $diam\left(G\right)=2$ and $k\ge 4$, then (12) $$\underset{k}{max}rc\left(G[H_1,\dots ,H_n]\right)=\left\{\begin{array}{cc}3,\hfill & \text{if every vertex of}G\text{lies on a triangle}\hfill \\ 4,\hfill & \text{otherwise.}\hfill \end{array}\right.$$(12) where the maximum is taken over all possible graphs $H_1,\dots ,H_n$ such that each $H_i$ has at least $k$ vertices.

Proof

Suppose that every vertex is contained in a triangle. This assumption together with $diam\left(G\right)=2$ implies that $G$ has a 3-walk between any $x,y\in V\left(G\right)$ (possibly $x=y$). So by Lemma 3 we have $rc\left(A\right)\le 3$ for any $G$-composition graph $A$.

Now we build a tight example. Replace a vertex $v\in V\left(G\right)$ with $m{K}_1$ where $m>2^{kdeg\left(v\right)}$, and every other vertex with $k{K}_1$, to get a $G$-composition graph $A$. Then $Q=V\left(m{K}_1\right)$ is co-neighboring and $\left|CN\left(Q\right)\right|=kdeg\left(v\right)$ so $src\left(A\right)\ge {\left|Q\right|}^{\frac{1}{\left|CN\left(Q\right)\right|}}>2$ by Lemma 1 (1), i.e. $src\left(A\right)\ge 3$. This implies $rc\left(A\right)\ge 3$, because any rainbow 2-coloring must also be a strong rainbow coloring.

If some vertex does not lie on any triangle, we are done by Theorem 2. □

3 Concluding remarks and open problems

We have proved $rc\left(G[H_1,\dots ,H_n]\right)=diam\left(G\right)$ when each $H_i$ has at least $diam\left(G\right)\ge 4$ vertices. We have also studied what happens when $diam\left(G\right)\le 3$, but we did not consider the case that some $H_i$ has less than $diam\left(G\right)$ vertices.

Theorem 3 (2) is a partial converse to Theorem 2 because if $G$ contains a 3-walk between any $x,y\in V\left(G\right)$ (possibly with $x=y$), then every vertex is contained in a triangle. These two statements are not equivalent, but it might be interesting to consider whether the weaker statement is enough. If it is, then the conclusion of Theorem 4 will also be true in the case $diam\left(G\right)=3$.