Rainbow Vertex Connection Numbers and Total Rainbow Connection Numbers of Middle and Total Graphs

Ma, Yingbin; Nie,  Kairui

doi:10.61091/ars157-04

Abstract

References

Ars Combinatoria

Volume 157
Pages: 45-52

Research article

Rainbow Vertex Connection Numbers and Total Rainbow Connection Numbers of Middle and Total Graphs

^¹, ^¹

¹College of Mathematics and Information Science Henan Normal University, Xinxiang 453007, P.R. China

Accepted: 19/07/2019
Published: 30/11/2023

Copyright Link
License

Abstract

A vertex-colouring of a graph $Γ$ is rainbow vertex connected if every pair of vertices $(u, v)$ in $Γ$ there is a $u - v$ path whose internal vertices have different colours. The rainbow vertex connection number of a graph $Γ$ , is the minimum number of colours needed to make $Γ$ rainbow vertex connected, denoted by $r v c (Γ)$ . Here, we study the rainbow vertex connection numbers of middle and total graphs. A total-colouring of a graph $Γ$ is total rainbow connected if every pair of vertices $(u, v)$ in $Γ$ there is a $u - v$ path whose edges and internal vertices have different colours. The total rainbow connection number of $Γ$ , is the minimum number of colours required to colour the edges and vertices of $Γ$ in order to make $Γ$ total rainbow connected, denoted by $t r c (Γ)$ . In this paper, we also research the total rainbow connection numbers of middle and total graphs.

Keywords: Rainbow vertex connection number, Total rainbow connection number, Middle graph, Total graph

1. Introduction

We consider finite and simple graphs only. That is, we do not allow the existence of loops and multiple edges. We follow the terminology and notation of [1] for those not described here. A graph $Γ$ is an ordered pair ( $V (Γ)$ , $E (Γ)$ ) consisting of a set $V (Γ)$ of vertices and a set $E (Γ)$ of edges. Let $P_{s}, C_{s}, K_{s}$ and $K_{1, s - 1}$ , denote the path, cycle, complete graph, and star graph with $s$ vertices, respectively.

An edge-colouring of a connected graph $Γ$ =( $V (Γ)$ , $E (Γ)$ ) is a mapping $c : E \to S$ , where $S$ is a set of colours. Usually, the set $S$ of colours is taken to be ${1, 2, \dots, t}$ , $t \in N$ . A $u - v$ path $P$ in an edge-coloured graph is defined as a rainbow path if it does not exist two edges on this path coloured the same. An edge-coloured graph $Γ$ is rainbow connected if any two vertices of $Γ$ are connected by a rainbow path. The rainbow connection number of a connected graph, denoted by $r c (Γ)$ , is the minimum $t$ for which are needed to make the graph rainbow connected. The concept of rainbow connection number was first introduced and researched by Chartrand et al. in [2].

Likewise the concept of rainbow connection number, Krivelevich and Yuster [3] put forward the concept of rainbow vertex connection number. A vertex-colouring of a connected graph $Γ = (V (Γ), E (Γ))$ is a mapping $c : V \to S$ , where $S$ is a set of colours. Usually, the set $S$ of colours is taken to be ${1, 2, \dots, t}$ , $t \in N$ . A path in a vertex-coloured graph is defined as a vertex rainbow path if its internal vertices are assigned distinct colours. A vertex-coloured graph $Γ$ is rainbow vertex connected if any two vertices of $Γ$ are connected by a vertex rainbow path, while the colouring is defined as rainbow vertex-colouring. The rainbow vertex connection number of $Γ$ , is the minimum $t$ for which are needed to make $Γ$ rainbow vertex connected, denoted by $r v c (Γ)$ . Let $Γ$ be a connected graph. The graph $Γ$ is complete, we have $r v c (Γ) = 0$ , and $r v c (Γ) \geq d i a m (Γ) - 1$ with equality if and only if the diameter of a graph is $1$ or $2$ . Moreover, if $Σ$ is a connected spanning subgraph of $Γ$ (that is $V (Γ) = V (Σ)$ ), then $r v c (Γ) \leq r v c (Σ)$ .

The research of rainbow connection has attracted tremendous attention in the literature, and many conclusions have been published, see [3,4,5,6,7,8,9,10,11] for example. For more results, The reader can refer to the survey [12] and a new monograph[13].

As a natural generalization, Uchizawa et al. [14] and Liu et al. [15] introdeced the concept of total rainbow connection number, respectively. A total-colouring of a graph $Γ$ is a mapping $c : V \cup E \to S$ , where $S$ is a set of colours. Usually, the set $S$ of colours is taken to be ${1, 2, \dots, t}$ , $t \in N$ . A $u - v$ path $P$ in a graph is defined as a total rainbow path if its internal vertices and edges are assigned distinct colours. A total-coloured graph $Γ$ is total rainbow connected if any two vertices in $Γ$ are connected by a total rainbow path, while the colouring is defined as total rainbow colouring. The total rainbow connection number of $Γ$ , is the minimum $t$ for which are needed to make $Γ$ total rainbow connected, denoted by $t r c (Γ)$ . A simple observation is that the graph $Γ$ is complete if and only if $t r c (Γ) = 1$ , otherwise $t r c (Γ) \geq 3$ . Moreover, $t r c (Γ) = 3$ if $d i a m (Γ) = 2$ and $r c (Γ) = 2$ . We also noticed some trivial fact that $t r c (Γ) \leq t r c (Σ)$ , where $Σ$ is a connected spanning subgraph of $Γ$ . For more results about the function $t r c (Γ)$ , the reader can see [16,17,18,19,20,21,22] for details.

Definition 1 ([23]). The middle graph $M (Γ)$ of a connected graph $Γ$ is defined as follows,

$(i)$ $V (M (Γ)) = V (Γ) \cup E (Γ)$ .

$(i i)$ Joining edges with those pairs of these vertices ( $x \in E (Γ), y \in E (Γ)$ ; $x \in E (Γ), y \in V (Γ)$ ) which is adjacent (incident) in $Γ$ .

In [24], Li investigated the rainbow connection numbers of middle graphs of $Γ$ , where $Γ ≅ P_{s}, C_{s}, K_{1, s}$ or $K_{s}$ . Here, we research the total rainbow connection numbers (rainbow vertex connection numbers) for the above middle graphs. Our first main result is stated as follows.

Theorem 1. $(i)$ Let $M (P_{s})$ be the middle graph of $P_{s}$ . Then $r v c (M (P_{s})) = s - 1$ and $t r c (M (P_{s})) = 2 s - 1$ .

$(i i)$ Let $M (C_{s})$ be the middle graph of $C_{s}$ . Then $r v c (M (C_{s})) = {\begin{cases} \frac{s}{2} & if s is even; \\ \frac{s + 1}{2} & if s is odd . \end{cases}$

and

$t r c (M (C_{s})) = {\begin{cases} s + 1 & if s is even; \\ s or s + 1 & if s is odd . \end{cases}$

$(i i i)$ Let $M (K_{1, s})$ be the middle graph of $K_{1, s}$ . Then $r v c (M (K_{1, s})) = s$ and $t r c (M (K_{1, s})) = 2 s$ .

$(i v)$ Let $M (K_{s})$ be the middle graph of $K_{s}$ . Then $r v c (M (K_{s})) = 1$ and $3 \leq t r c (M (K_{s})) \leq s + 1$ .

Definition 2 ([25]). The total graph $T (Γ)$ of a graph $Γ$ is defined as follows.

$(i)$ $V (T (Γ)) = V (Γ) \cup E (Γ)$ .

$(i i)$ Joining edges with those pairs of these vertices ( $x \in E (Γ), y \in E (Γ)$ ; $x \in E (Γ), y \in V (Γ)$ ; $x \in V (Γ), y \in V (Γ)$ ) which is adjacent (incident) in $Γ$ .

Li [24] considered the rainbow connection numbers of total graphs of $Γ$ , where $Γ ≅ P_{s}, C_{s}, K_{1, s}$ or $K_{s}$ . Here, we also consider the total rainbow connection numbers (rainbow vertex connection numbers) for the above total graphs. Our second main result is stated as follows.

Theorem 2. $(i)$ Let $T (P_{s})$ be the total graph of $P_{s}$ . Then $r v c (T (P_{s})) = s - 2$ and $t r c (T (P_{s})) = 2 s - 3$ .

$(i i)$ Let $T (C_{s})$ be the total graph of $C_{s}$ . Then $r v c (T (C_{s})) = {\begin{cases} \frac{s - 2}{2} o r \frac{s}{2} & if s is even; \\ \frac{s - 1}{2} o r \frac{s + 1}{2} & if s is odd . \end{cases}$ and

$t r c (T (C_{s})) = {\begin{cases} s - 1, s o r s + 1 & if s is even; \\ s or s + 1 & if s is odd . \end{cases}$

$(i i i)$ Let $T (K_{1, s})$ be the total graph of $K_{1, s}$ . Then $r v c (T (K_{1, s})) = 1, t r c (T (K_{1, 2})) = 3, t r c (T (K_{1, 3})) = 4$ and $t r c (T (K_{1, s})) = 5$ with $s \geq 4$ .

$(i v)$ Let $T (K_{s})$ be the total graph of $K_{s}$ . Then $r v c (T (K_{s})) = 1$ and $3 \leq t r c (T (K_{s})) \leq s + 1$ .

2. Proof of Theorem 1

Proposition 1. Let $M (P_{s})$ be the middle graph of $P_{s}$ . Then $r v c (M (P_{s})) = s - 1$ and $t r c (M (P_{s})) = 2 s - 1$ .

Proof. The graph $M (P_{s})$ is depicted in Figure 1. First we prove that $r v c (M (P_{s})) = s - 1$ . Let $c$ be a vertex-colouring of $M (P_{s})$ defined as follows: $c (u_{1}) = 1, c (v_{i}) = c (u_{i + 1}) = i$ for $1 \leq i \leq s - 2$ , $c (v_{s - 1}) = c (u_{s}) = s - 1$ . We will see that $M (P_{s})$ is rainbow vertex connected, and so $r v c (M (P_{s})) \leq s - 1$ . On the other hand, since $d i a m (M (P_{s})) = s$ , this implies $r v c (M (P_{s})) \geq s - 1$ , and so $r v c (M (P_{s})) = s - 1$ .

Now we prove that $t r c (M (P_{s})) = 2 s - 1$ . Let $c$ be a total-colouring of $M (P_{s})$ defined as follows: $c (u_{1} v_{1}) = 1, c (v_{i} u_{i + 1}) = c (v_{i} v_{i + 1}) = c (u_{i + 1} v_{i + 1}) = i + 1$ for $1 \leq i \leq s - 2$ , $c (v_{s - 1} u_{s}) = s, c (u_{1}) = s + 1$ , $c (v_{i}) = c (u_{i + 1}) = s + i$ for $1 \leq i \leq s - 2$ , $c (v_{s - 1}) = c (u_{s}) = 2 s - 1$ . We will see that $M (P_{s})$ is total rainbow connected. Thus $t r c (M (P_{s})) \leq 2 s - 1$ . On the other hand, since $d i a m (M (P_{s})) = s$ , this implies $t r c (M (P_{s})) \geq 2 s - 1$ , which follows that $t r c (M (P_{s})) = 2 s - 1$ .

Proposition 2. Let $M (C_{s})$ be the middle graph of $C_{s}$ . Then $r v c (M (C_{s})) = {\begin{cases} \frac{s}{2} & if s is even; \\ \frac{s + 1}{2} & if s is odd . \end{cases}$

and

$t r c (M (C_{s})) = {\begin{cases} s + 1 & if s is even; \\ s or s + 1 & if s is odd . \end{cases}$

Proof. The graph $M (C_{s})$ is depicted in Figure 2. First we prove that $r v c (M (C_{s})) = {\begin{cases} \frac{s}{2} & if s is even; \\ \frac{s + 1}{2} & if s is odd . \end{cases}$ Suppose $s$ is even with $s = 2 t$ . Since $d i a m (M (C_{s})) = t + 1$ , we have $r v c (M (C_{s})) \geq t$ . Let $c$ be a vertex-colouring of $M (C_{s})$ defined as follows: $c (u_{i}) = c (v_{i}) = i$ for $1 \leq i \leq t$ , $c (u_{i}) = c (v_{i}) = i - t$ for $t + 1 \leq i \leq s$ . We know that $M (C_{s})$ is rainbow vertex connected, and so $r v c (M (C_{s})) \leq t$ . Thus $r v c (M (C_{s})) = t$ .

Suppose $s$ is odd with $s = 2 t + 1$ . Since $d i a m (M (C_{s})) = t + 1$ , it follows that $r v c (M (C_{s})) \geq t$ . Now we show that $r v c (M (C_{s})) \neq t$ . To the contrary, assume that $M (C_{s})$ exists a rainbow vertex-colouring $c$ with $t$ colours. Considering $u_{1}$ and $u_{t + 1}$ , $u_{1} v_{1} v_{2} \dots v_{t - 1} v_{t} u_{t + 1}$ must be a vertex rainbow $u_{1} - u_{t + 1}$ path. Without loss of generality, let $c (v_{i}) = i$ for $1 \leq i \leq t$ . Considering $u_{2}$ and $u_{t + 2}$ , $u_{2} v_{2} v_{3} \dots v_{t} v_{t + 1} u_{t + 2}$ must be a vertex rainbow $u_{2} - u_{t + 2}$ path. Thus $c (v_{t + 1}) = 1$ . By the same steps, we know that $c (v_{t + i}) = i$ for $2 \leq i \leq t$ . Considering $u_{t + 2}$ and $u_{1}$ , $u_{t + 2} v_{t + 2} v_{t + 3} \dots v_{s - 1} v_{s} u_{1}$ must be a vertex rainbow $u_{t + 2} - u_{1}$ path, and so $c (v_{s}) = 1$ . But then, there does not exist a vertex rainbow path connecting $u_{t + 3}$ and $u_{2}$ , a contradiction. Thus $r v c (M (C_{s})) \neq t$ . Let $c$ be a vertex-colouring of $M (C_{n})$ defined as follows: $c (v_{i}) = c (u_{i}) = i$ for $1 \leq i \leq t$ , $c (v_{i}) = c (u_{i}) = i - t$ for $t + 1 \leq i \leq 2 t, c (v_{s}) = c (u_{s}) = t + 1$ . We will see that $M (C_{s})$ is rainbow vertex connected, and so $r v c (M (C_{s})) = t + 1$ .

Now we prove that $t r c (M (C_{s})) = {\begin{cases} s + 1 & if s is even; \\ s or s + 1 & if s is odd . \end{cases}$

Suppose $s$ is even with $s = 2 t$ . Since $d i a m (M (C_{s})) = t + 1$ , we have $t r c (M (C_{s})) \geq 2 t + 1$ . Let $c$ be a total-colouring of $M (C_{s})$ defined as follows: $c (u_{1} v_{1}) = c (v_{s} v_{1}) = 1, c (u_{i} v_{i}) = c (v_{i - 1} v_{i}) = i$ for $2 \leq i \leq t$ , $c (u_{i} v_{i}) = c (v_{i - 1} v_{i}) = i - t$ for $t + 1 \leq i \leq s$ , assign all other edges with $t + 1$ , $c (v_{i}) = c (u_{i}) = t + i + 1$ for $1 \leq i \leq t$ , $c (v_{i}) = c (u_{i}) = i + 1$ for $t + 1 \leq i \leq s$ . We will see that $M (C_{s})$ is total rainbow connected, and so $t r c (M (C_{s})) \leq s + 1$ . Thus $t r c (M (C_{s})) = s + 1$ .

Suppose $s$ is odd with $s = 2 t + 1$ . Let $c$ be a total-colouring of $M (C_{s})$ defined as follows: $c (u_{1} v_{1}) = c (v_{s} v_{1}) = 1, c (u_{1} v_{s}) = t + 1, c (v_{i} u_{i}) = c (v_{i - 1} v_{i}) = i$ and $c (v_{i - 1} u_{i}) = t + 1$ for $2 \leq i \leq t$ , $c (v_{t} v_{t + 1}) = c (v_{t} u_{t + 1}) = c (u_{t + 1} v_{t + 1}) = t + 1$ , $c (v_{t + i} u_{t + i + 1}) = c (v_{t + i} v_{t + i + 1}) = c (v_{t + i + 1} u_{t + i + 1}) = i$ for $1 \leq i \leq t$ , $c (v_{i}) = c (u_{i}) = t + i + 1$ for $1 \leq i \leq t$ , $c (v_{i}) = c (u_{i}) = i + 1$ for $t + 1 \leq i \leq s$ . We obtained that $M (C_{s})$ is total rainbow connected. Since $d i a m (M (C_{s})) = t + 1$ , we have $t r c (M (C_{s})) \geq 2 t + 1 = s$ , which follows that $s \leq t r c (M (C_{s})) \leq s + 1$ .

Proposition 3. Let $M (K_{1, s})$ be the middle graph of $K_{1, s}$ . Then $r v c (M (K_{1, s})) = s$ and $t r c (M (K_{1, s})) = 2 s$ .

Proof. The graph $M (K_{1, s})$ is depicted in Figure 3. First we prove that $r v c (M (K_{1, s})) = s$ . Since the cut vertices must be coloured by different colours, we have $r v c (M (K_{1, s})) \geq s$ . Assign $u_{i}$ with $i$ for $1 \leq i \leq s$ , and assign all other vertices with $1$ . We will see that $M (K_{1, s})$ is rainbow vertex connected, and so $r v c (M (P_{s})) \leq s$ . This implies $r v c (M (K_{1, s})) = s$ .

Figure 3. The middle graph of $K_{1, s}$ .

Now we prove that $t r c (M (K_{1, s})) = 2 s$ . Since the cut edges and cut vertices must be coloured by different colours, we obtain $t r c (M (K_{1, s})) \geq 2 s$ . Let $c$ be a total-colouring of $M (K_{1, s})$ defined as follows: $c (u_{i} v_{i}) = i$ for $1 \leq i \leq s$ , $c (u u_{1}) = s, c (u u_{i}) = i - 1$ for $2 \leq i \leq s$ , $c (u_{i} u_{i + 1}) = i + 2$ for $1 \leq i \leq s - 2$ , $c (u_{s - 1} u_{s}) = 1, c (u_{i} u_{j}) = j - 1$ for $1 \leq i, j \leq s$ and $j - i \geq 2$ , $c (u_{i}) = s + i$ for $1 \leq i \leq s$ , assign all other vertices with $s + 1$ . Note that for any two different vertices $v_{i}$ and $v_{j}$ for $1 \leq i, j \leq s$ , we know that $v_{i} u_{i} u_{j} v_{j}$ is a total rainbow $v_{i} - v_{j}$ path. Thus $M (K_{1, s})$ is total rainbow connected, and hence $t r c (M (K_{1, s})) \leq 2 s$ . Therefore, $t r c (M (K_{1, s})) = 2 s$ .

Proposition 4. Let $M (K_{s})$ be the middle graph of $K_{s}$ . Then $r v c (M (K_{s})) = 1$ and $3 \leq t r c (M (K_{s})) \leq s + 1$ .

Proof. Note that $d i a m (M (K_{s})) = 2$ , we have $r v c (M (K_{s})) = 1$ . Now we prove that $3 \leq t r c (M (K_{s})) \leq s + 1$ . Obviously, $t r c (M (K_{s})) \geq 3$ since $d i a m (M (K_{s})) = 2$ . The structure of $M (K_{s})$ is depicted as follows: $M (K_{s}) = H_{1} \cup H_{2} \cup \dots \cup H_{s}$ , where $H_{i} ≅ K_{s}$ for $1 \leq i \leq s$ , and for any $i, j \in {1, 2, \dots, s}$ , $H_{i}$ and $H_{j}$ only intersect a different vertex. Let $c$ be a total-colouring of $M (K_{s})$ defined as follows: For any $e \in H_{i}, c (e) = i$ , assign $s + 1$ to all vertices. We will see that $M (K_{s})$ is total rainbow connected, and so $t r c (M (K_{s})) \leq s + 1$ . Hence $3 \leq t r c (M (K_{s})) \leq s + 1$ .

Combining Propositions 1, 2, 3, 4, Theorem 1 is immediate.

3. Proof of Theorem 2

Proposition 5. Let $T (P_{s})$ be the total graph of $P_{s}$ . Then $r v c (T (P_{s})) = s - 2$ and $t r c (T (P_{s})) = 2 s - 3$ .

Proof. The graph $T (P_{s})$ is depicted in Figure 4. First we prove that $r v c (T (P_{s})) = s - 2$ . Since $d i a m (T (P_{s})) = s - 1$ , we have $r v c (T (P_{s})) \geq s - 2$ . Let $c$ be a vertex-colouring of $T (P_{s})$ defined as follows: $c (v_{i}) = c (u_{i + 1}) = i$ for $1 \leq i \leq s - 2$ , assign all other vertices with $1$ . We will see that $T (P_{s})$ is rainbow vertex connected, and so $r v c (T (P_{s})) \leq s - 2$ . Thus $r v c (T (P_{s})) = s - 1$ .

Now we prove that $t r c (T (P_{s})) = 2 s - 3$ . Let $c$ be a total-colouring of $T (P_{s})$ defined as follows: $c (u_{i} v_{i}) = c (u_{i} u_{i + 1}) = c (v_{i} u_{i + 1}) = i$ for $1 \leq i \leq s - 1$ , assign all other edges with $1$ , $c (v_{i}) = c (u_{i + 1}) = s + i - 1$ for $1 \leq i \leq s - 2$ , all other vertices coloured with $s$ . We will see that $T (P_{s})$ is total rainbow connected with the above total-colouring. Thus $t r c (T (P_{s})) \leq 2 s - 3$ . On the other hand, since $d i a m (T (P_{s})) = s - 1$ , this implies $t r c (T (P_{s})) \geq 2 s - 3$ . This follows that $t r c (T (P_{s})) = 2 s - 3$ .

Proposition 6. Let $T (C_{s})$ be the total graph of $C_{s}$ . Then $r v c (T (C_{s})) = {\begin{cases} \frac{s}{2} - 1 o r \frac{s}{2} & if s is even; \\ \frac{s - 1}{2} o r \frac{s + 1}{2} & if s is odd . \end{cases}$

and

$t r c (T (C_{s})) = {\begin{cases} s - 1, s o r s + 1 & if s is even; \\ s or s + 1 & if s is odd . \end{cases}$

Proof. By [24], we know that $d i a m (T (C_{s})) = {\begin{cases} \frac{s}{2} & if s is even; \\ \frac{s + 1}{2} & if s is odd . \end{cases}$ On the other hand, note that $M (C_{s})$ is a connected spanning subgraph of $T (C_{s})$ , this proposition follows from Proposition 2.

Proposition 7. Let $T (K_{1, s})$ be the total graph of $K_{1, s}$ . Then $r v c (T (K_{1, s})) = 1, t r c (T (K_{1, 2})) = 3, t r c (T (K_{1, 3})) = 4$ and $t r c (T (K_{1, s})) = 5$ with $s \geq 4$ .

Proof. Since $d i a m (T (K_{1, s})) = 2$ , we have $r v c (T (K_{1, s})) = 1$ and $t r c (T (K_{1, s})) \geq 3$ for $s \geq 2$ .

Suppose $s = 2$ . We can easily verify that the total-colouring shown in Figure 5(a) is total rainbow. Thus $t r c (T (K_{1, 2})) = 3$ .

Suppose $s = 3$ . Let $c$ be a total-colouring of $T (K_{1, 3})$ defined as follows: $c (u v_{1}) = c (u u_{1}) = 1, c (u v_{2}) = c (u u_{2}) = 2, c (u v_{3}) = c (u u_{3}) = 3$ , assign all other edges with $1$ , and assign all vertices with $4$ . We can easily verify that $T (K_{1, 3})$ is total rainbow connected with the above total-colouring, and so $t r c (T (K_{1, 3})) \leq 4$ . Now we only need to prove that $t r c (T (K_{1, 3})) \neq 3$ . To the contrary, assume that $T (K_{1, 3})$ exists a total rainbow colouring with $3$ colours. Considering $v_{1}$ and $v_{2}$ , the total rainbow $v_{1} - v_{2}$ path must be $v_{1} u v_{2}$ . Without loss of generality, assume that $c (v_{1} u) = 1, c (u) = 2, c (u v_{2}) = 3$ . Considering $v_{1}$ and $v_{3}$ , the total rainbow $v_{1} - v_{3}$ path must be $v_{1} u v_{3}$ . Thus $c (u v_{3}) = 3$ . But then, there is no total rainbow $v_{2} - v_{3}$ path, a contradiction. Hence $t r c (T (K_{1, 3})) \neq 3$ , and so $t r c (T (K_{1, 3})) = 4$ .

Figure 5. The total graph of $K_{1, s}$ .

Suppose $s \geq 4$ . Let $c$ be a total-colouring of $T (K_{1, s})$ defined as follows: assign $1$ to the edges $u v_{i}$ for $1 \leq i \leq s$ , assign $2$ to the edges $u_{i} v_{i}$ for $1 \leq i \leq s$ , assign $3$ to all other edges, assign $4$ to $u$ , and assign $5$ to all other vertices. We will see that $T (K_{1, s})$ is total rainbow connected with the above total-colouring. Thus $t r c (T (K_{1, s})) \leq 5$ . Now we only need to prove that $t r c (T (K_{1, s})) \neq 4$ . To the contrary, assume that $T (K_{1, s})$ exists a total rainbow colouring with $4$ colours. Considering $v_{1}$ and $v_{2}$ , $v_{1} u v_{2}$ must be a total rainbow $v_{1} - v_{2}$ path. Without loss of generality, assume that $c (u) = 1, c (v_{1} u) = 2, c (u v_{2}) = 3$ . Considering $v_{1}$ and $v_{3}$ , $v_{1} u v_{3}$ must be a total rainbow $v_{1} - v_{3}$ path. Thus $c (u v_{3}) = 4$ , otherwise there is no total rainbow $v_{2} - v_{3}$ path. Considering $v_{1}$ and $v_{4}$ , $v_{1} u v_{4}$ must be a total rainbow $v_{1} - v_{4}$ path. Hence $c (u v_{4}) = 3$ or $4$ . But then there is no total rainbow $v_{2} - v_{4}$ path or $v_{3} - v_{4}$ path. Hence $t r c (T (K_{1, s})) \neq 4$ , and so $t r c (T (K_{1, s})) = 5$ .

Proposition 8. Let $T (K_{s})$ be the total graph of $K_{s}$ . Then $r v c (T (K_{s})) = 1$ and $3 \leq t r c (T (K_{s})) \leq s + 1$ .

Proof. Note that $d i a m (T (K_{s})) = 2$ . Then $r v c (T (K_{s})) = 1$ . Obviously, $M (K_{s})$ is a connected spanning subgraph of $T (K_{s})$ . By Proposition 4, we have $3 \leq t r c (T (K_{s})) \leq s + 1$ .

Combining Propositions 5, 6, 7, 8, Theorem 2 is immediate.

4. Conclusion

The concept of total rainbow connection number was proposed in recent years. Moreover, Chen et al.[16] proved that the calculating of $t r c (Γ)$ is NP-hard. Subsequently, there is a great interest towards determining the total rainbow connection numbers of some graph classes. In this paper, we mainly consider the total rainbow connection numbers of middle and total graphs.

Conflict of Interest

The authors declare no conflict of interests.

Acknowledgement

This work was supported by the NSFC (No.11701157), Foundation of Henan Educational Committee (No.18A110023), and the Foundation of Henan Normal University (No.2019QK06).

References:

Bondy, J.A. and Murty, U.S.R., 2008. Graph Theory. Springer, Berlin.[Google Scholor]
Chartrand, G., Johns, G.L., McKeon, K.A. and Zhang, P., 2008. Rainbow connection in graphs. Mathematica bohemica, 133(1), pp.85-98.[Google Scholor]
Krivelevich, M. and Yuster, R., 2010. The rainbow connection of a graph is (at most) reciprocal to its minimum degree. Journal of Graph Theory, 63(3), pp.185-191.[Google Scholor]
Sunil Chandran, L., Das, A., Rajendraprasad, D. and Varma, N.M., 2012. Rainbow connection number and connected dominating sets. Journal of Graph Theory, 71(2), pp.206-218.[Google Scholor]
Huang, X., Li, X. and Shi, Y., 2015. Note on the hardness of rainbow connections for planar and line graphs. Bulletin of the Malaysian Mathematical Sciences Society, 38(3), pp.1235-1241.[Google Scholor]
Huang, X., Li, X., Shi, Y., Yue, J. and Zhao, Y., 2014. Rainbow connections for outerplanar graphs with diameter 2 and 3. Applied Mathematics and Computation, 242, pp.277-280.[Google Scholor]
Lei, H., Li, S., Liu, H. and Shi, Y., 2018. Rainbow vertex connection of digraphs. Journal of Combinatorial Optimization, 35, pp.86-107.[Google Scholor]
Li, X., Liu, S., Chandran, L.S., Mathew, R. and Rajendraprasad, D., 2012. Rainbow connection number and connectivity. The Electronic Journal Of Combinatorics, pp.P20.[Google Scholor]
Li, X. and Shi, Y., 2013. Rainbow connection in 3-connected graphs. Graphs and Combinatorics, 29(5), pp.1471-1475.[Google Scholor]
Li, X. and Shi, Y., 2013. On the rainbow vertex-connection. Discussiones Mathematicae Graph Theory, 33(2), pp.307-313.[Google Scholor]
Schiermeyer, I., 2013. On minimally rainbow k-connected graphs. Discrete Applied Mathematics, 161(4-5), pp.702-705.[Google Scholor]
Li, X., Shi, Y. and Sun, Y., 2013. Rainbow connections of graphs: A survey. Graphs and combinatorics, 29, pp.1-38.[Google Scholor]
Li, X. and Sun, Y., 2012. Rainbow connections of graphs. Springer Science & Business Media.[Google Scholor]
Uchizawa, K., Aoki, T., Ito, T., Suzuki, A. and Zhou, X., 2013. On the rainbow connectivity of graphs: complexity and FPT algorithms. Algorithmica, 67, pp.161-179.[Google Scholor]
Liu, H., Mestre, \^{A}. and Sousa, T., 2014. Total rainbow k-connection in graphs. Discrete Applied Mathematics, 174, pp.92-101.[Google Scholor]
Chen, L., Huo, B. and Ma, Y., 2016. Hardness results for total rainbow connection of graphs. Discussiones Mathematicae Graph Theory, 36(2), pp.355-362.[Google Scholor]
Jiang, H., Li, X. and Zhang, Y., 2016. Upper bounds for the total rainbow connection of graphs. Journal of Combinatorial Optimization, 32, pp.260-266.[Google Scholor]
Lei, H., Liu, H., Magnant, C. and Shi, Y., 2018. Total rainbow connection of digraphs. Discrete Applied Mathematics, 236, pp.288-305.[Google Scholor]
Ma, Y., Chen, L. and Li, H., 2017. Graphs with small total rainbow connection number. Frontiers of Mathematics in China, 12, pp.921-936.[Google Scholor]
Ma, Y., Chen, L. and Li, H., 2017. Graphs with small total rainbow connection number. Frontiers of Mathematics in China, 12, pp.921-936.[Google Scholor]
Ma, Y.B., Chen, L., Li, H.Z. and Li, H.F., 2016. The total rainbow connection numbers of cubic graphs. utilitas mathematica, 99, pp.143-150.[Google Scholor]
Sun, Y., 2015. On rainbow total-coloring of a graph. Discrete Applied Mathematics, 194, pp.171-177.[Google Scholor]
Hamada, T. and Yoshimura, I., 1976. Traversability and connectivity of the middle graph of a graph. Discrete Mathematics, 14(3), pp.247-255.[Google Scholor]
Li, F., 2013. Rainbow connection numbers of middle and total graphs. Utilitas Mathematica, 91, 243-260.[Google Scholor]
Behzad, M., 1967, July. A criterion for the planarity of the total graph of a graph. In Mathematical Proceedings of the Cambridge Philosophical Society (Vol. 63, No. 3, pp. 679-681). Cambridge University Press.[Google Scholor]

[1] Bondy, J.A. and Murty, U.S.R., 2008. Graph Theory. Springer, Berlin.[Google Scholor]

[2] Chartrand, G., Johns, G.L., McKeon, K.A. and Zhang, P., 2008. Rainbow connection in graphs. Mathematica bohemica, 133(1), pp.85-98.[Google Scholor]

[3] Krivelevich, M. and Yuster, R., 2010. The rainbow connection of a graph is (at most) reciprocal to its minimum degree. Journal of Graph Theory, 63(3), pp.185-191.[Google Scholor]

[4] Sunil Chandran, L., Das, A., Rajendraprasad, D. and Varma, N.M., 2012. Rainbow connection number and connected dominating sets. Journal of Graph Theory, 71(2), pp.206-218.[Google Scholor]

[5] Huang, X., Li, X. and Shi, Y., 2015. Note on the hardness of rainbow connections for planar and line graphs. Bulletin of the Malaysian Mathematical Sciences Society, 38(3), pp.1235-1241.[Google Scholor]

[6] Huang, X., Li, X., Shi, Y., Yue, J. and Zhao, Y., 2014. Rainbow connections for outerplanar graphs with diameter 2 and 3. Applied Mathematics and Computation, 242, pp.277-280.[Google Scholor]

[7] Lei, H., Li, S., Liu, H. and Shi, Y., 2018. Rainbow vertex connection of digraphs. Journal of Combinatorial Optimization, 35, pp.86-107.[Google Scholor]

[8] Li, X., Liu, S., Chandran, L.S., Mathew, R. and Rajendraprasad, D., 2012. Rainbow connection number and connectivity. The Electronic Journal Of Combinatorics, pp.P20.[Google Scholor]

[9] Li, X. and Shi, Y., 2013. Rainbow connection in 3-connected graphs. Graphs and Combinatorics, 29(5), pp.1471-1475.[Google Scholor]

[10] Li, X. and Shi, Y., 2013. On the rainbow vertex-connection. Discussiones Mathematicae Graph Theory, 33(2), pp.307-313.[Google Scholor]

[11] Schiermeyer, I., 2013. On minimally rainbow k-connected graphs. Discrete Applied Mathematics, 161(4-5), pp.702-705.[Google Scholor]

[12] Li, X., Shi, Y. and Sun, Y., 2013. Rainbow connections of graphs: A survey. Graphs and combinatorics, 29, pp.1-38.[Google Scholor]

[13] Li, X. and Sun, Y., 2012. Rainbow connections of graphs. Springer Science & Business Media.[Google Scholor]

[14] Uchizawa, K., Aoki, T., Ito, T., Suzuki, A. and Zhou, X., 2013. On the rainbow connectivity of graphs: complexity and FPT algorithms. Algorithmica, 67, pp.161-179.[Google Scholor]

[15] Liu, H., Mestre, \^{A}. and Sousa, T., 2014. Total rainbow k-connection in graphs. Discrete Applied Mathematics, 174, pp.92-101.[Google Scholor]

[16] Chen, L., Huo, B. and Ma, Y., 2016. Hardness results for total rainbow connection of graphs. Discussiones Mathematicae Graph Theory, 36(2), pp.355-362.[Google Scholor]

[17] Jiang, H., Li, X. and Zhang, Y., 2016. Upper bounds for the total rainbow connection of graphs. Journal of Combinatorial Optimization, 32, pp.260-266.[Google Scholor]

[18] Lei, H., Liu, H., Magnant, C. and Shi, Y., 2018. Total rainbow connection of digraphs. Discrete Applied Mathematics, 236, pp.288-305.[Google Scholor]

[19] Ma, Y., Chen, L. and Li, H., 2017. Graphs with small total rainbow connection number. Frontiers of Mathematics in China, 12, pp.921-936.[Google Scholor]

[20] Ma, Y., Chen, L. and Li, H., 2017. Graphs with small total rainbow connection number. Frontiers of Mathematics in China, 12, pp.921-936.[Google Scholor]

[21] Ma, Y.B., Chen, L., Li, H.Z. and Li, H.F., 2016. The total rainbow connection numbers of cubic graphs. utilitas mathematica, 99, pp.143-150.[Google Scholor]

[22] Sun, Y., 2015. On rainbow total-coloring of a graph. Discrete Applied Mathematics, 194, pp.171-177.[Google Scholor]

[23] Hamada, T. and Yoshimura, I., 1976. Traversability and connectivity of the middle graph of a graph. Discrete Mathematics, 14(3), pp.247-255.[Google Scholor]

[24] Li, F., 2013. Rainbow connection numbers of middle and total graphs. Utilitas Mathematica, 91, 243-260.[Google Scholor]

[25] Behzad, M., 1967, July. A criterion for the planarity of the total graph of a graph. In Mathematical Proceedings of the Cambridge Philosophical Society (Vol. 63, No. 3, pp. 679-681). Cambridge University Press.[Google Scholor]

Contents

Ars Combinatoria

Rainbow Vertex Connection Numbers and Total Rainbow Connection Numbers of Middle and Total Graphs

Abstract

1. Introduction

2. Proof of Theorem 1

3. Proof of Theorem 2

4. Conclusion

Conflict of Interest

Acknowledgement

References:

Information

Guidelines

CP Initiatives

Follow CP