JACODESMATH / ISSN 2148-838X

J. Algebra Comb. Discrete Appl.
2(3) • 157-161

Received: 12 April 2015; Accepted: 31 May 2015
DOI 10.13069/jacodesmath.80607

Journal of Algebra Combinatorics Discrete Structures and Applications

The rainbow vertex-index of complementary graphs∗

Research Article

Fengnan Yanling1∗∗, Zhao Wang1∗∗∗, Chengfu Ye1§, Shumin Zhang1§§

1. Qinghai Normal University

Abstract: A vertex-colored graph G is rainbow vertex-connected if two vertices are connected by a path whose
internal vertices have distinct colors. The rainbow vertex-connection number of a connected graph
G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow
vertex-connected. If for every pair u, v of distinct vertices, G contains a vertex-rainbow u−v geodesic,
then G is strongly rainbow vertex-connected. The minimum k for which there exists a k-coloring of G
that results in a strongly rainbow-vertex-connected graph is called the strong rainbow vertex number
srvc(G) of G. Thus rvc(G) ≤ srvc(G) for every nontrivial connected graph G. A tree T in G is called
a rainbow vertex tree if the internal vertices of T receive different colors. For a graph G = (V, E) and
a set S ⊆ V of at least two vertices, an S-Steiner tree or a Steiner tree connecting S (or simply, an
S-tree) is a such subgraph T = (V ′, E′) of G that is a tree with S ⊆ V ′. For S ⊆ V (G) and |S| ≥ 2,
an S-Steiner tree T is said to be a rainbow vertex S-tree if the internal vertices of T receive distinct
colors. The minimum number of colors that are needed in a vertex-coloring of G such that there is a
rainbow vertex S-tree for every k-set S of V (G) is called the k-rainbow vertex-index of G, denoted by
rvxk(G). In this paper, we first investigate the strong rainbow vertex-connection of complementary
graphs. The k-rainbow vertex-index of complementary graphs are also studied.

2010 MSC: 05C15, 05C40

Keywords: Strong rainbow vertex-connection number, Complementary graph, Rainbow vertex S-tree, k-rainbow
vertex-index

1. Introduction

The graphs considered in this paper are finite undirected and simple graphs. We follow the notation
of Bondy and Murty [1], unless otherwise stated. For a graph G, let V (G), E(G), n(G), m(G), and G,
respectively, be the set of vertices, the set of edges, the order, the size, and the complement graph of G.

∗ Supported by the National Science Foundation of China (No. 11161037, 11101232, 11461054) and the Science
Found of Qinghai Province (No. 2014-ZJ-907).
∗∗ E-mail: fengnanyanlin@yahoo.com (Corresponding Author)
∗∗∗ E-mail: wangzhao380@yahoo.com
§ E-mail: yechf@qhnu.edu.cn
§§ E-mail: zhsm_0926@sina.com

157



The rainbow vertex-index of complementary graphs

Let G be a nontrivial connected graph on which an edge-coloring c : E(G) → {1, 2, · · · , n}, n ∈ N,
is defined, where adjacent edges may be colored the same. A path is rainbow if no two edges of it are
colored the same. An edge-coloring graph G is rainbow connected if any two vertices are connected by
a rainbow path. Clearly, if a graph is rainbow connected, it must be connected, whereas any connected
graph has a trivial edge-coloring that makes it rainbow connected; just color each edge with a distinct
color. Thus, in [4] L. Chen, X. Li, H. Lian defined the rainbow connection number of a connected graph
G, denoted by rc(G), as the smallest number of colors that are needed in order to make G rainbow
connected. They showed that rc(G) ≥ diam(G) where diam(G) denotes the diameter of G. For more
results on the rainbow connection, we refer to the survey paper [2],[3],[4] and [12], and a new book [10]
of Li and Sun.

In [8], Krivelevich and Yuster proposed the concept of rainbow vertex-connection. A vertex-colored
graph G is rainbow vertex-connected if two vertices are connected by a path whose internal vertices have
distinct colors. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is
the smallest number of colors that are needed in order to make G rainbow vertex-connected. For more
results on the rainbow vertex-connection, we refer to the survey paper [5] and [9]. An easy observation is
that if G is of order n, then rvc(G) ≤ n− 2 and rvc(G) = 0 if and only if G is a complete graph. Notice
that rvc(G) ≥ diam(G) − 1 with equality if the diameter is 1 or 2.

If for every pair u, v of distinct vertices, G contains a vertex-rainbow u − v geodesic, then G is
strong rainbow vertex-connected. The definition of strongly rainbow vertex-connected was defined by
Li et al. in [11]. The minimum k for which there exists a k-coloring of G that results in a strongly
rainbow vertex-connected graph is called the strong rainbow vertex-connection number srvc(G) of G.
Thus rc(G) ≤ srvc(G) for every nontrivial connected graph G.

If G is a nontrivial connected graph of order n whose diameter is diam(G), then

diam(G) − 1 ≤ rvc(G) ≤ srvc(G) ≤ n−s, (1)

where s denote the number of pendent vertices in G.

Proposition 1.1. Let G be a nontrivial connected graph of order n. Then

(a) srvc(G) = 0 if and only if G is a complete graph;

(b) srvc(G) = 1 if and only if diam(G) = 2 if and only if rvc(G) = 1.

A tree T in G is called a rainbow vertex tree if the internal vertices of T receive different colors. For a
graph G = (V, E) and a set S ⊆ V of at least two vertices, an S-Steiner tree or a Steiner tree connecting
S (or simply, an S-tree) is a such subgraph T = (V ′, E′) of G that is a tree with S ⊆ V ′. For more
problems on S-Steiner tree, we refer to [6] and [7].

For S ⊆ V (G) and |S| ≥ 2, an S-Steiner tree T is said to be a rainbow vertex S-tree if the internal
vertices of T receive distinct colors. The minimum number of colors that are needed in an vertex-coloring
of G such that there is a rainbow vertex S-tree for every k-set S of V (G) is called the k-rainbow vertex-
index of G, denoted by rvxk(G). The vertex-rainbow index of a graph was first defined by Yaping Mao
in [13].

2. The strong rainbow vertex-connection of complementary
graphs

In this section, we investigate the rainbow vertex-connection number of a graph G according to some
constraints to its complement G. We give some conditions to guarantee that srvc(G) is bounded by a
constant.

We investigate the rainbow vertex-connection number of connected complement graphs of graphs
with diameter at least 3.

158



Fengnan Yanling et al.

Theorem 2.1. If G is a connected graph with diam(G) ≥ 3, then

srvc(G) =

{
1, if diam(G) ≥ 4;
2, if diam(G) = 3.

Proof. We choose a vertex x with eccG(x) = diam(G) = d ≥ 3. Let NiG(x) = {v : dG(x, v) = i} where
0 ≤ i ≤ d. So N0G(x) = {x}, N

1
G(x) = NG(x) as usual. Then

⋃
0≤i≤d N

i
G(x) is a vertex partition of V (G)

with |NiG(x)| = ni. Let A =
⋃

i is even N
i
G(x), B =

⋃
i is odd N

i
G(x). For example, see Figure 1, a graph

with diam(G) = 5.

So, if d = 2k(k ≥ 2), then A =
⋃

0≤i≤d is even N
i
G(x), B =

⋃
1≤i≤d−1 is odd N

i
G(x); if d = 2k + 1(k ≥

2) then A =
⋃

0≤i≤d−1 is even N
i
G(x), B =

⋃
1≤i≤d is odd N

i
G(x). Then by the definition of complement

graphs, we know that G[A] (G[B]) contains a spanning complete k1-partite subgraph(complete k2-partite
subgraph) where k1 = dd+12 e (k2 = d

d
2
e). For example, see Figure 1, G[A] contains a spanning complete

tripartite subgraph Kn0,n2,n4, G[B] contains a spanning complete tripartite subgraph Kn1,n3,n5.

Figure 1. Graphs for the proof of Theorem 2.

First of all, we see that G must be connected, since otherwise, diam(G) ≤ 2, contradicting the
condition diam(G) ≥ 3.

Case 1. d ≥ 5.
In this case, k1, k2 ≥ 3. We will show that diam(Ḡ) ≤ 2 in this case. For u, v ∈ V (G), we consider

the following cases:

Subcase 1.1. u, v ∈ A or u, v ∈ B.
If u, v ∈ A, then u, v is contained in the spanning complete k1-partite subgraph of G[A]. Thus

dG(u, v) ≤ 2. The same is true for u, v ∈ B.
Subcase 1.2. u ∈ A and v ∈ B.
If u = x, v ∈ B, then u is adjacent to all vertices in G[B] \ N1G(x). So dG(u, v) = 1 for v ∈

G[B] \N1G(x). For v ∈ N
1
G(x), let P = ux3v, where x3 ∈ N

3
G(x). Clearly, dG(u, v) = 2.

If u 6= x, without loss of generality, we assume that u ∈ N2G(x) and v ∈ N
1
G(x). Let Q = ux5v, where

x5 ∈ N5G(x). Thus dG(u, v) = 2.

From the above, we conclude that diam(G) ≤ 2. So, by Proposition 1(b), we have srvc(G) = 1.

159



The rainbow vertex-index of complementary graphs

Case 2. d = 4.

It is obvious that A = N0G(x) ∪ N
2
G(x) ∪ N

4
G(x), B = N

1
G(x) ∪ N

3
G(x). So G[A](G[B]) contains a

spanning complete 3-partite subgraph Kn0,n2,n4 (complete bipartite subgraph Kn1,n3). So, we will show
that diam(G) ≤ 2.

Subcase 2.1. u, v ∈ A or u, v ∈ B.
If u, v ∈ A, then u, v is contained in the spanning complete k1-partite subgraph of G[A]. Thus

dG(u, v) ≤ 2. If u, v ∈ B, then u, v is contained in the spanning complete bipartite subgraph of G[B].
Also we have dG(u, v) ≤ 2.

Subcase 2.2. u ∈ A and v ∈ B.
If u = x, v ∈ B, then u is adjacent to all vertices in N3G(x). For v ∈ N

1
G(x), let P = ux3v, where

x3 ∈ N3G(x). Clearly, dG(u, v) = 2. So dG(u, v) ≤ 2.
If u 6= x, then we assume that u ∈ N2G(x) and v ∈ N

1
G(x). Let Q = ux4v, where x4 ∈ N

4
G(x). Thus

dG(u, v) = 2. Suppose u ∈ N
4
G(x) and v ∈ N

3
G(x). Let R = ux1v, where x1 ∈ N

1
G(x). Thus dG(u, v) = 2.

If u ∈ N2G(x) and v ∈ N
3
G(x), then S = uxv is a path of length 2. Then diam(G) ≤ 2. So, by Proposition

1, we have srvc(G) = 1.

Case 3. d = 3.

In this case, A = N0G(x) ∪ N
2
G(x), B = N

1
G(x) ∪ N

3
G(x). So G[A] contains a spanning complete

bipartite subgraph Kn0,n2. So, we give G a vertex-coloring as follows: color vertex x with 1 and color all
vertices of N3G(x) with 2. It is easy to see that for any u ∈ N

2
G(x), v ∈ N

1
G(x), there is a rainbow {1, 2}

path connecting them in G. So srvc(G) = 2 in this case.

For the case of diam(G) = 2, srvc(G) can be very large since diam(G) may be very large. For
example, let G = Kn \ E(Cn), where Cn is a cycle of length n in Kn. Then G = Cn and srvc(G) ≥
diam(G) − 1 = dn

2
e− 1 by (1).

3. The k-rainbow vertex-index of complete multipartite graphs

Theorem 3.1. Let Kn1,n2,···nl be a complete multipartite graph. If k < 2`, then rvxk = 1; If k ≥ 2`,
then rvxk = 2. Where S = {v1, v2, · · ·vk} (that is the rainbow S-tree we choose) and Vni, (1 ≤ i ≤ l) are
the vertices of the partition of Kn1,n2,···n`.

Proof. If k < 2`, then we can find a partition Vni, (1 ≤ i ≤ l) of Kn1,n2,···nl with Vni ∩ S ≤ 1. If
Vni ∩ S = ∅, then we can choose a vertex v ∈ Vni as the root vertex of the rainbow S tree and all the
other vertices are leaves. So rvxk(Kn1,n2,···n` ) = 1. If Vni ∩S = 1, then we choose the vertex v ∈ Vni as
the root vertex of the rainbow S tree, and all the other vertices are leaves. So rvxk(Kn1,n2,···n` ) = 1.

If k ≥ 2` and there exists Vni such that |S ∩ Vni| ≤ 1, then we can choose the vertex v in Vni
as the root of the rainbow tree and all the other vertices are the leaves the same as when k < 2`. So
rvxk(Kn1,n2,···nl ) = 1.

Suppose k ≥ 2` and |S ∩Vni| ≥ 2 for any Vni. Now we give a rainbow vertex-coloring as follows.

c(Vni ) =

{
1, if 1 ≤ i ≤ `− 1;
2, if i = `.

Next we prove it is a k-rainbow vertex-coloring. Choose one vertex v in Vn` as the root vertex of the
rainbow tree. Obviously v is adjacent to all the vertices in Vn1 ∩S, Vn2 ∩S, . . . Vn`−1 ∩S. Then choose a
vertex in v′ ∈ Vn1. Since v′ is adjacent to all the remaining vertices in Vn` ∩ S, one can prove that the
tree is rainbow S-tree.

160



Fengnan Yanling et al.

4. The k-rainbow vertex-index of complementary graphs

Theorem 4.1. If G is a connected graph with diam(G) ≥ 3, then rvxk(Ḡ) ≤ 2 and the bound is tight.

Proof. We choose a vertex x with eccG(x) = diam(G) = d ≥ 3 as Figure 1. Then G[A](G[B]) contains
a spanning complete k1-partite subgraph (complete k2-partite subgraph). If the rainbow S-tree contains
in G[A](G[B]), then rvxk(Ḡ) ≤ 2 by Theorem 3.1. Now we consider the rainbow S-tree does not contain
in G[A] or G[B]. If S ∩ N1G(G) = ∅, then we choose x as the root vertex, and all the other vertices are
the leaves. So one can prove that there is a rainbow S-tree. Suppose S ∩ N1G(G) 6= ∅. Now we give a
rainbow vertex-coloring as follows. {

c(x) = 1,
c(v) = 2, v ∈ V (G)\x.

We choose the vertex x as the root of the rainbow tree. We know x is adjacent to all the vertices in
N

j
G(x) ∩ S, (j ∈{2, 3, 4, · · ·}), and there must be a v ∈ N

j
G(x), (j ∈{2m + 1 and m ≥ 1}) such that v is

adjacent to N1G(x) ∩S. one can prove that the tree is rainbow S-tree.
Let G is a connected graph of diam(G) = 3. We have rvxk(Ḡ) = 2, so the bound is tight.

Acknowledgement: The authors are very grateful to the referees’ valuable comments and sugges-
tions, which helped greatly to improve the presentation of this paper.

References

[1] J. A. Bondy and U. S. R. Murty, Graph theory, GTM 244, Springer, 2008.
[2] G. Chartrand, G. L. Johns, K. A. McKeon and P. Zhang, Rainbow connection in graphs, Math.

Bohem., 133, 85–98, 2008.
[3] G. Chartrand, G. L. Johns, K. A. McKeon and P. Zhang, The rainbow connectivity of a graph,

Networks, 54(2), 75–81, 2009.
[4] L. Chen, X. Li and H. Lian, Nordhaus-Gaddum-type theorem for rainbow connection number of

graphs, Graphs Combin., 29(5), 1235–1247, 2013.
[5] L. Chen, X. Li and M. Liu, Nordhaus-Gaddum-type theorem for the rainbow vertex connection number

of a graph, Utilitas Math., 86, 335–340, 2011.
[6] X. Cheng and D. Du, Steiner trees in industry, Kluwer Academic Publisher, Dordrecht, 2001.
[7] D. Du and X. Hu, Steiner tree problems in computer communication networks, World Scientific, 2008.
[8] M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its

minimum degree three, J. Graph Theory, 63(3), 185-191, 2010.
[9] X. Li and Y. Shi, On the rainbow vertex-connection, Discuss. Math. Graph Theory, 33(2), 307–313,

2013.
[10] X. Li and Y. Sun, Rainbow connections of graphs, SpringerBriefs in Math., Springer, New York,

2012.
[11] X. Li, Y. Mao and Y. Shi, The strong rainbow vertex-connection of graphs, Utilitas Math., 93, 213–

223, 2014.
[12] X. Li, Y. Shi and Y. Sun, Rainbow connections of graphs–A survey, Graphs Combin., 29(1), 1-38,

2013.
[13] Y. Mao, The vertex-rainbow index of a graph, arXiv:1502.00151v1 [math.CO], 31 Jan 2015.
[14] E. A. Nordhaus and J. W. Gaddum, On complementary graphs, Amer. Math. Monthly, 63, 175–177,

1956.

161


	Introduction
	The strong rainbow vertex-connection of complementary graphs
	The k-rainbow vertex-index of complete multipartite graphs
	The k-rainbow vertex-index of complementary graphs
	References