Menu
A vertex-colouring of a graph \(\Gamma\) is rainbow vertex connected if every pair of vertices \((u,v)\) in \(\Gamma\) there is a \(u-v\) path whose internal vertices have different colours. The rainbow vertex connection number of a graph \(\Gamma\), is the minimum number of colours needed to make \(\Gamma\) rainbow vertex connected, denoted by \(rvc(\Gamma)\). Here, we study the rainbow vertex connection numbers of middle and total graphs. A total-colouring of a graph \(\Gamma\) is total rainbow connected if every pair of vertices \((u,v)\) in \(\Gamma\) there is a \(u-v\) path whose edges and internal vertices have different colours. The total rainbow connection number of \(\Gamma\), is the minimum number of colours required to colour the edges and vertices of \(\Gamma\) in order to make \(\Gamma\) total rainbow connected, denoted by \(trc(\Gamma)\). In this paper, we also research the total rainbow connection numbers of middle and total graphs.
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 \(\Gamma\) is an ordered pair (\(V(\Gamma)\), \(E(\Gamma)\)) consisting of a set \(V(\Gamma)\) of vertices and a set \(E(\Gamma)\) 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 \(\Gamma\)=(\(V(\Gamma)\), \(E(\Gamma)\)) 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,\ldots,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 \(\Gamma\) is rainbow connected if any two vertices of \(\Gamma\) are connected by a rainbow path. The rainbow connection number of a connected graph, denoted by \(rc(\Gamma)\), 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 \(\Gamma=(V(\Gamma), E(\Gamma))\) 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,\ldots,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 \(\Gamma\) is rainbow vertex connected if any two vertices of \(\Gamma\) are connected by a vertex rainbow path, while the colouring is defined as rainbow vertex-colouring. The rainbow vertex connection number of \(\Gamma\), is the minimum \(t\) for which are needed to make \(\Gamma\) rainbow vertex connected, denoted by \(rvc(\Gamma)\). Let \(\Gamma\) be a connected graph. The graph \(\Gamma\) is complete, we have \(rvc(\Gamma)=0\), and \(rvc(\Gamma)\geq diam(\Gamma)-1\) with equality if and only if the diameter of a graph is \(1\) or \(2\). Moreover, if \(\Sigma\) is a connected spanning subgraph of \(\Gamma\)(that is \(V(\Gamma)=V(\Sigma)\)), then \(rvc(\Gamma)\leq rvc(\Sigma)\).
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 \(\Gamma\) 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,\ldots,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 \(\Gamma\) is total rainbow connected if any two vertices in \(\Gamma\) are connected by a total rainbow path, while the colouring is defined as total rainbow colouring. The total rainbow connection number of \(\Gamma\), is the minimum \(t\) for which are needed to make \(\Gamma\) total rainbow connected, denoted by \(trc(\Gamma)\). A simple observation is that the graph \(\Gamma\) is complete if and only if \(trc(\Gamma)=1\), otherwise \(trc(\Gamma)\geq 3\). Moreover, \(trc(\Gamma)=3\) if \(diam(\Gamma)=2\) and \(rc(\Gamma)=2\). We also noticed some trivial fact that \(trc(\Gamma)\leq trc(\Sigma)\), where \(\Sigma\) is a connected spanning subgraph of \(\Gamma\). For more results about the function \(trc(\Gamma)\), the reader can see [16,17,18,19,20,21,22] for details.
Definition 1 ([23]). The middle graph \(M(\Gamma)\) of a connected graph \(\Gamma\) is defined as follows,
\(\mathrm{(i)}\) \(V(M(\Gamma))=V(\Gamma)\cup E(\Gamma)\).
\(\mathrm{(ii)}\) Joining edges with those pairs of these vertices (\(x\in E(\Gamma), y\in E(\Gamma)\) ; \(x\in E(\Gamma), y\in V(\Gamma)\)) which is adjacent (incident) in \(\Gamma\).
In [24], Li investigated the rainbow connection numbers of middle graphs of \(\Gamma\), where \(\Gamma\cong 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. \(\mathrm{(i)}\) Let \(M(P_{s})\) be the middle graph of \(P_{s}\). Then \(rvc(M(P_{s}))=s-1\) and \(trc(M(P_{s}))=2s-1\).
\(\mathrm{(ii)}\) Let \(M(C_{s})\) be the middle graph of \(C_{s}\). Then \[rvc(M(C_{s})) = \left\{ \begin{array}{ll} {s\over 2} & \textrm{if $s$ is even};\\ {s+1\over 2}& \textrm{if $s$ is odd}. \end{array} \right.\]
and
\[trc(M(C_{s})) = \left\{ \begin{array}{ll} s+1 & \textrm{if $s$ is even};\\ s~\textrm{or} ~s+1 & \textrm{if $s$ is odd}. \end{array} \right.\]
\(\mathrm{(iii)}\) Let \(M(K_{1,s})\) be the middle graph of \(K_{1,s}\). Then \(rvc(M(K_{1,s}))=s\) and \(trc(M(K_{1,s}))=2s\).
\(\mathrm{(iv)}\) Let \(M(K_{s})\) be the middle graph of \(K_{s}\). Then \(rvc(M(K_{s}))=1\) and \(3\leq trc(M(K_{s}))\leq s+1\).
Definition 2 ([25]). The total graph \(T(\Gamma)\) of a graph \(\Gamma\) is defined as follows.
\(\mathrm{(i)}\) \(V(T(\Gamma))=V(\Gamma)\cup E(\Gamma)\).
\(\mathrm{(ii)}\) Joining edges with those pairs of these vertices (\(x\in E(\Gamma), y\in E(\Gamma)\) ; \(x\in E(\Gamma), y\in V(\Gamma)\) ; \(x\in V(\Gamma), y\in V(\Gamma)\)) which is adjacent (incident) in \(\Gamma\).
Li [24] considered the rainbow connection numbers of total graphs of \(\Gamma\), where \(\Gamma\cong 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. \(\mathrm{(i)}\) Let \(T(P_{s})\) be the total graph of \(P_{s}\). Then \(rvc(T(P_{s}))=s-2\) and \(trc(T(P_{s}))=2s-3\).
\(\mathrm{(ii)}\) Let \(T(C_{s})\) be the total graph of \(C_{s}\). Then \[rvc(T(C_{s})) = \left\{ \begin{array}{ll} {s-2\over 2}~ or~ {s\over 2} & \textrm{if $s$ is even};\\ {s-1\over 2} ~or ~{s+1\over 2}& \textrm{if $s$ is odd}. \end{array} \right.\] and
\[trc(T(C_{s})) = \left\{ \begin{array}{ll} s-1, s ~or~ s+1 & \textrm{if $s$ is even};\\ s~\textrm{or}~ s+1 & \textrm{if $s$ is odd}. \end{array} \right.\]
\(\mathrm{(iii)}\) Let \(T(K_{1,s})\) be the total graph of \(K_{1,s}\). Then \(rvc(T(K_{1,s}))=1, trc(T(K_{1,2}))=3, trc(T(K_{1,3}))=4\) and \(trc(T(K_{1,s}))=5\) with \(s\geq 4\).
\(\mathrm{(iv)}\) Let \(T(K_{s})\) be the total graph of \(K_{s}\). Then \(rvc(T(K_{s}))=1\) and \(3\leq trc(T(K_{s}))\leq s+1\).
Proposition 1. Let \(M(P_{s})\) be the middle graph of \(P_{s}\). Then \(rvc(M(P_{s}))=s-1\) and \(trc(M(P_{s}))=2s-1\).
Proof. The graph \(M(P_{s})\) is depicted in Figure 1. First we prove that \(rvc(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 \(rvc(M(P_{s}))\leq s-1\). On the other hand, since \(diam(M(P_{s}))=s\), this implies \(rvc(M(P_{s}))\geq s-1\), and so \(rvc(M(P_{s}))=s-1\).
Now we prove that \(trc(M(P_{s}))=2s-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})=2s-1\). We will see that \(M(P_{s})\) is total rainbow connected. Thus \(trc(M(P_{s}))\leq 2s-1\). On the other hand, since \(diam(M(P_{s}))=s\), this implies \(trc(M(P_{s}))\geq 2s-1\), which follows that \(trc(M(P_{s}))=2s-1\).
Proposition 2. Let \(M(C_{s})\) be the middle graph of \(C_{s}\). Then \[rvc(M(C_{s})) = \left\{ \begin{array}{ll} {s\over 2} & \textrm{if $s$ is even};\\ {s+1\over 2}& \textrm{if $s$ is odd}. \end{array} \right.\]
and
\[trc(M(C_{s})) = \left\{ \begin{array}{ll} s+1 & \textrm{if $s$ is even};\\ s~\textrm{or}~ s+1 & \textrm{if $s$ is odd}. \end{array} \right.\]
Proof. The graph \(M(C_{s})\) is depicted in Figure 2. First we prove that \[rvc(M(C_{s})) = \left\{ \begin{array}{ll} {s\over 2} & \textrm{if $s$ is even};\\ {s+1\over 2}& \textrm{if $s$ is odd}. \end{array} \right.\] Suppose \(s\) is even with \(s=2t\). Since \(diam(M(C_{s}))=t+1\), we have \(rvc(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 \(rvc(M(C_{s}))\leq t\). Thus \(rvc(M(C_{s}))=t\).
Suppose \(s\) is odd with \(s=2t+1\). Since \(diam(M(C_{s}))=t+1\), it follows that \(rvc(M(C_{s}))\geq t\). Now we show that \(rvc(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}\cdots 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}\cdots 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}\cdots 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 \(rvc(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 2t, c(v_{s})=c(u_{s})=t+1\). We will see that \(M(C_{s})\) is rainbow vertex connected, and so \(rvc(M(C_{s}))=t+1\).
Now we prove that \[trc(M(C_{s})) = \left\{ \begin{array}{ll} s+1 & \textrm{if $s$ is even};\\ s~\textrm{or}~ s+1 & \textrm{if $s$ is odd}. \end{array} \right.\]
Suppose \(s\) is even with \(s=2t\). Since \(diam(M(C_{s}))=t+1\), we have \(trc(M(C_{s}))\geq 2t+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 \(trc(M(C_{s}))\leq s+1\). Thus \(trc(M(C_{s}))=s+1\).
Suppose \(s\) is odd with \(s=2t+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 \(diam(M(C_{s}))=t+1\), we have \(trc(M(C_{s}))\geq 2t+1=s\), which follows that \(s\leq trc(M(C_{s}))\leq s+1\).
Proposition 3. Let \(M(K_{1,s})\) be the middle graph of \(K_{1,s}\). Then \(rvc(M(K_{1,s}))\\=s\) and \(trc(M(K_{1,s}))=2s\).
Proof. The graph \(M(K_{1,s})\) is depicted in Figure 3. First we prove that \(rvc(M(K_{1,s}))=s\). Since the cut vertices must be coloured by different colours, we have \(rvc(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 \(rvc(M(P_{s}))\leq s\). This implies \(rvc(M(K_{1,s}))=s\).
Now we prove that \(trc(M(K_{1,s}))=2s\). Since the cut edges and cut vertices must be coloured by different colours, we obtain \(trc(M(K_{1,s}))\geq 2s\). 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(uu_{1})=s, c(uu_{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 \(trc(M(K_{1,s}))\leq 2s\). Therefore, \(trc(M(K_{1,s}))=2s\).
Proposition 4. Let \(M(K_{s})\) be the middle graph of \(K_{s}\). Then \(rvc(M(K_{s}))\\=1\) and \(3\leq trc(M(K_{s}))\leq s+1\).
Proof. Note that \(diam(M(K_{s}))=2\), we have \(rvc(M(K_{s}))=1\). Now we prove that \(3\leq trc(M(K_{s}))\leq s+1\). Obviously, \(trc(M(K_{s}))\geq 3\) since \(diam(M(K_{s}))=2\). The structure of \(M(K_{s})\) is depicted as follows: \(M(K_{s})=H_{1}\cup H_{2}\cup \cdots \cup H_{s}\), where \(H_{i}\cong K_{s}\) for \(1\leq i\leq s\), and for any \(i,j\in \{1, 2,\cdots, 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 \(trc(M(K_{s}))\leq s+1\). Hence \(3\leq trc(M(K_{s}))\leq s+1\).
Combining Propositions 1, 2, 3, 4, Theorem 1 is immediate.
Proposition 5. Let \(T(P_{s})\) be the total graph of \(P_{s}\). Then \(rvc(T(P_{s}))=s-2\) and \(trc(T(P_{s}))=2s-3\).
Proof. The graph \(T(P_{s})\) is depicted in Figure 4. First we prove that \(rvc(T(P_{s}))=s-2\). Since \(diam(T(P_{s}))=s-1\), we have \(rvc(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 \(rvc(T(P_{s}))\leq s-2\). Thus \(rvc(T(P_{s}))=s-1\).
Now we prove that \(trc(T(P_{s}))=2s-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 \(trc(T(P_{s}))\leq 2s-3\). On the other hand, since \(diam(T(P_{s}))=s-1\), this implies \(trc(T(P_{s}))\geq 2s-3\). This follows that \(trc(T(P_{s}))=2s-3\).
Proposition 6. Let \(T(C_{s})\) be the total graph of \(C_{s}\). Then \[rvc(T(C_{s})) = \left\{ \begin{array}{ll} {s\over 2}-1~ or~ {s\over 2} & \textrm{if $s$ is even};\\ {s-1\over 2} ~or ~{s+1\over 2}& \textrm{if $s$ is odd}. \end{array} \right.\]
and
\[trc(T(C_{s})) = \left\{ \begin{array}{ll} s-1, s ~or~ s+1 & \textrm{if $s$ is even};\\ s~\textrm{or}~ s+1 & \textrm{if $s$ is odd}. \end{array} \right.\]
Proof. By [24], we know that \[diam(T(C_{s})) = \left\{ \begin{array}{ll} {s\over 2} & \textrm{if $s$ is even};\\ {s+1\over 2}& \textrm{if $s$ is odd}. \end{array} \right.\] 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 \(rvc(T(K_{1,s}))\\=1, trc(T(K_{1,2}))=3, trc(T(K_{1,3}))=4\) and \(trc(T(K_{1,s}))=5\) with \(s\geq 4\).
Proof. Since \(diam(T(K_{1,s}))=2\), we have \(rvc(T(K_{1,s}))=1\) and \(trc(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 \(trc(T(K_{1,2}))=3\).
Suppose \(s=3\). Let \(c\) be a total-colouring of \(T(K_{1,3})\) defined as follows: \(c(uv_{1})=c(uu_{1})=1, c(uv_{2})=c(uu_{2})=2, c(uv_{3})=c(uu_{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 \(trc(T(K_{1,3}))\leq 4\). Now we only need to prove that \(trc(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}uv_{2}\). Without loss of generality, assume that \(c(v_{1}u)=1, c(u)=2, c(uv_{2})=3\). Considering \(v_{1}\) and \(v_{3}\), the total rainbow \(v_{1}-v_{3}\) path must be \(v_{1}uv_{3}\). Thus \(c(uv_{3})=3\). But then, there is no total rainbow \(v_{2}-v_{3}\) path, a contradiction. Hence \(trc(T(K_{1,3}))\neq 3\), and so \(trc(T(K_{1,3}))=4\).
Suppose \(s\geq 4\). Let \(c\) be a total-colouring of \(T(K_{1,s})\) defined as follows: assign \(1\) to the edges \(uv_{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 \(trc(T(K_{1,s}))\leq 5\). Now we only need to prove that \(trc(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}uv_{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(uv_{2})=3\). Considering \(v_{1}\) and \(v_{3}\), \(v_{1}uv_{3}\) must be a total rainbow \(v_{1}-v_{3}\) path. Thus \(c(uv_{3})=4\), otherwise there is no total rainbow \(v_{2}-v_{3}\) path. Considering \(v_{1}\) and \(v_{4}\), \(v_{1}uv_{4}\) must be a total rainbow \(v_{1}-v_{4}\) path. Hence \(c(uv_{4})=3\) or \(4\). But then there is no total rainbow \(v_{2}-v_{4}\) path or \(v_{3}-v_{4}\) path. Hence \(trc(T(K_{1,s}))\neq 4\), and so \(trc(T(K_{1,s}))=5\).
Proposition 8. Let \(T(K_{s})\) be the total graph of \(K_{s}\). Then \(rvc(T(K_{s}))=1\) and \(3\leq trc(T(K_{s}))\leq s+1\).
Proof. Note that \(diam(T(K_{s}))=2\). Then \(rvc(T(K_{s}))=1\). Obviously, \(M(K_{s})\) is a connected spanning subgraph of \(T(K_{s})\). By Proposition 4, we have \(3\leq trc(T(K_{s}))\leq s+1\).
Combining Propositions 5, 6, 7, 8, Theorem 2 is immediate.
The concept of total rainbow connection number was proposed in recent years. Moreover, Chen et al.[16] proved that the calculating of \(trc(\Gamma)\) 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.
The authors declare no conflict of interests.
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).