The Rainbow Vertex-Connection Number of Star Fan Graphs


CAUCHY –Jurnal Matematika Murni dan Aplikasi 
Volume 5(3) (2018), Pages 112-116 
p-ISSN: 2086-0382; e-ISSN: 2477-3344 

Submitted: 28 August 2018 Reviewed: 08 October 2018 Accepted: 30 November 2018 
DOI: http://dx.doi.org/10.18860/ca.v5i3.5516 

The Rainbow Vertex-Connection Number of Star Fan Graphs 

Ariestha Widyastuty Bustan1, A.N.M. Salman2 

1Mathematics Department, Faculty of Mathematics and Natural Sciences, Universitas 
Pasifik Morotai 

2Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural 
Sciences, Institut Teknologi Bandung  

 

Email: ariesthawidyastutybustan@gmail.com , msalman@math.itb.ac.id  

ABSTRACT  

A vertex-colored graph 𝐺 = (𝑉(𝐺), 𝐸(𝐺)) is said to be rainbow vertex-connected, if for every two vertices 

𝑒 and 𝑣 in 𝑉(𝐺), there exists a 𝑒 βˆ’ 𝑣  path with all internal vertices have distinct colors. The rainbow vertex-
connection number of 𝐺, denoted by π‘Ÿπ‘£π‘(𝐺), is the smallest number of colors needed to make 𝐺 rainbow 
vertex-connected. In this paper, we determine the rainbow vertex-connection number of star fan graphs. 

 
Keywords: Rainbow Vertex-Coloring; Rainbow Vertex-Connection Number; Star Fan Graph; Fan  

INTRODUCTION  

All graph considered in this paper are finite, simple, and undirected. We follow the 

notation and terminology of Diestel [1]. A vertex-colored graph 𝐺 = (𝑉(𝐺), 𝐸(𝐺)) is said 

to be rainbow vertex-connected, if for every two vertices 𝑒 and 𝑣 in 𝑉(𝐺), there exists a 
𝑒 βˆ’ 𝑣  path with all internal vertices have distinct colors. The rainbow vertex-connection 
number of 𝐺, denoted by π‘Ÿπ‘£π‘(𝐺), is the smallest number of colors needed to make 𝐺 
rainbow vertex-connected. It was introduced by Krivelevich and Yuster [2]. 

Let 𝐺 be a connected graph, 𝑛 be the size of 𝐺, and diameter of 𝐺 denoted by 
π‘‘π‘–π‘Žπ‘š(𝐺), then they stated that 
    π‘‘π‘–π‘Žπ‘š(𝐺) βˆ’ 1 ≀ π‘Ÿπ‘£π‘(𝐺) ≀ 𝑛 βˆ’ 2    (1) 
Besides that, if 𝐺 has 𝑐 cut vertices, then  

π‘Ÿπ‘£π‘(𝐺) β‰₯ 𝑐      (2) 
In fact, by coloring the cut vertices with distinct colors, we obtain  π‘Ÿπ‘£π‘(𝐺) β‰₯ 𝑐. It is defined 
that     π‘Ÿπ‘£π‘(𝐺) = 0 if 𝐺 is a complete graph 

There are many interesting results about rainbow vertex-connection numbers. 
Some of them were stated by Li and Liu[3] and Simamora and Salman[4] and Bustan [5]. 
Li and Liu determined the rainbow vertex-connection number of a cycle 𝐢𝑛 of order 𝑛 β‰₯
3. Based on it, they proved that for a connected graph 𝐺 with a block decomposition 
𝐡1, 𝐡2, … , π΅π‘˜ and 𝑐 cut vertices, π‘Ÿπ‘£π‘(𝐡1) + π‘Ÿπ‘£π‘(𝐡2) + β‹― + π‘Ÿπ‘£π‘(π΅π‘˜ ) + 𝑑.  In 2015 Simamora 
and Salman determined the rainbow vertex-connection number of pencil graph. In 2016 
Bustan determined the rainbow vertex-connection number of star cycle graph. 

In this paper, we introduce a new class of graph that we called star fan graphs and 
we determine the rainbow vertex-connection number of them. Star fan graphs are divided 
into two classes based on the selection of a vertex of the fan graph ie a vertex with 𝑛 degree 
and vertex with 3 degree. 

mailto:ariesthawidyastutybustan@gmail.com
mailto:msalman@math.itb.ac.id


The Rainbow Vertex-Connection Number of Star Fan Graphs  

Ariestha Widyastuty Bustan 113 

 

 
Figure 1. 𝑆(6, 𝐹6, 𝑣𝑖,1)   

 

 
Figure 2. 𝑆(6, 𝐹6, 𝑣𝑖,7) 

 

RESULTS AND DISCUSSION  

Definition 1. Let π‘š and 𝑛 be two integers at least 3, π‘†π‘š be a star with π‘š + 1 
vertices. 𝐹𝑛  be a fan with 𝑛 + 1 vertices, 𝑣 ∈ 𝑉(𝐹𝑛 ) and 𝑣 is a vertex with 𝑛 degree. A star 
fan graph is a graph obtained by embedding a copy of 𝐹𝑛  to each pendant of π‘†π‘š, denoted 
by 𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,1) 𝑖 ∈ [1, π‘š], such that the vertex set and the edge set, respectively, as 

follows. 

𝑉 (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,1)) = {𝑣𝑖,𝑗 |𝑖 ∈ [1, π‘š], 𝑗 ∈ [1, π‘š + 1]} βˆͺ {π‘£π‘š+1},    

𝐸 (𝑆(π‘š, 𝐹𝑛, 𝑣𝑖,1)) = {π‘£π‘š+1𝑣𝑖,1|𝑖

∈ [1, π‘š]} βˆͺ {𝑣𝑖,1𝑣𝑖,𝑗 | 𝑖 ∈ [1, π‘š], 𝑗 ∈ [2, π‘š + 1]} βˆͺ {𝑣𝑖,𝑗 𝑣𝑖,𝑗+1| 𝑖 ∈ [1, π‘š], 𝑗

∈ [2, π‘š]}  
 



The Rainbow Vertex-Connection Number of Star Fan Graphs  

Ariestha Widyastuty Bustan 114 

Theorem 1. Let π‘š and 𝑛 be two integers at least 3 and 𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,1) be a star fan graph, 

then 

π‘Ÿπ‘£π‘ (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,1))=π‘š + 1 

Proof. 
Based on equation (2), we have 

 π‘Ÿπ‘£π‘ (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,1)) β‰₯ 𝑐 = π‘š + 1    (3) 

 

In order to proof π‘Ÿπ‘£π‘ (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,1)) ≀ π‘š + 1, define a vertex-coloring 

𝛼: 𝑉(𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖1)) β†’ [1, π‘š + 1] as follows. 

𝛼(𝑣𝑖,𝑗 ) = {
π’Š,   π‘“π‘œπ‘Ÿ 𝑗 = 1 

π’Ž + 𝟏,   π‘œπ‘‘β„Žπ‘’π‘Ÿπ‘ 
 

 

We are able to find a rainbow path for every pair vertices 𝑒 and 𝑣 in 𝑉 (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,1)) as 

shown in table 1 
 

Tabel 1. The rainbow vertex 𝑒 βˆ’ 𝑣 path for graph 𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,1) 

𝒖 𝒗 Condition Rainbow-vertex path 
𝑒 is adjacent to v Trivial 

π’—π’Š,𝒋 π’—π’Œ,𝒍 π’Š, π’Œ ∈ [𝟏, π’Ž] 
𝒋, 𝒍 ∈ [𝟏, π’Ž + 𝟏] 

π’—π’Š,𝒋, π’—π’Š,𝟏, π’—π’Ž+𝟏, π’—π’Œ,𝟏,π’—π’Œ,𝒍 

 
So we conclude that 

 π‘Ÿπ‘£π‘ (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,1)) ≀ π‘š + 1    (4) 

 

From equation (3) and (4), we have π‘Ÿπ‘£π‘ (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,1)) = π‘š + 1 

 
Definition 2. Let π‘š and 𝑛 be two integers at least 3, π‘†π‘š be a star with π‘š + 1 

vertices. 𝐹𝑛  be a fan with 𝑛 + 1 vertices, 𝑣 ∈ 𝑉(𝐹𝑛 ) and 𝑣 is a vertex with 3 degree. A star 
fan graph is a graph obtained by embedding a copy of 𝐹𝑛  to each pendant of π‘†π‘š, denoted 
by 𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,𝑗 ) 𝑖 ∈ [1, π‘š], 𝑗 ∈ [2, π‘š] such that the vertex set and the edge set, respectively, 

as follows. 

𝑉 (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,𝑗 )) = {𝑣𝑖,𝑗 |𝑖 ∈ [1, π‘š], 𝑗 ∈ [, π‘š + 1]} βˆͺ {π‘£π‘š+1},    

𝐸 (𝑆(π‘š, 𝐹𝑛, 𝑣𝑖,𝑗 )) = {π‘£π‘š+1𝑣𝑖,𝑗 |𝑖 ∈ [1, π‘š], 𝑗

∈ [2, π‘š + 1]} βˆͺ {𝑣𝑖,1𝑣𝑖,𝑗 | 𝑖 ∈ [1, π‘š], 𝑗 ∈ [2, π‘š + 1]} βˆͺ {𝑣𝑖,𝑗 𝑣𝑖,𝑗+1| 𝑖 ∈ [1, π‘š], 𝑗

∈ [2, π‘š]} 
Theorem 2. Let π‘š and 𝑛 be two integers at least 3 and 𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,𝑗 ) be a star fan graph, 

then 

π‘Ÿπ‘£π‘ (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,𝑗 ))=π‘š + 2 

Proof. 
ο‚· Case 1. π’Ž = πŸ‘ 

Based on equation (1), we have π‘Ÿπ‘£π‘ (𝑆(3, 𝐹3, 𝑣𝑖,4)) β‰₯ π‘‘π‘–π‘Žπ‘š βˆ’ 1 = 6 βˆ’ 1 = 5. We may 

define a rainbow vertex 5-coloring on  𝑆(π‘š, 𝐹, 𝑣𝑖,7) as shown in Figure 2. 



The Rainbow Vertex-Connection Number of Star Fan Graphs  

Ariestha Widyastuty Bustan 115 

 
Figure 3. 𝑆(3, 𝐹3, 𝑣𝑖,4) 

ο‚· Case 2. π’Ž β‰₯ πŸ’ 

Based on equation (2), we have π‘Ÿπ‘£π‘ (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,𝑗 )) β‰₯ π‘š + 1. Suppose that There is a 

rainbow vertex π‘š + 1-coloring on 𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,𝑗 ). Without loss of generality, color the 

vertices as follows: 
 𝛽′(π‘£π‘š+1) = π‘š + 1 
 𝛽′(𝑣𝑖,π‘š+1) = 𝑖, 𝑖 ∈ [1, π‘š] 

 
Look at the vertex 𝑣1,2 and 𝑣2,2 who can not use the same color. To obtain rainbow vertex 
path between them, should be passed the path of 𝑣1,2, 𝑣1,1, 𝑣1,π‘š+1, π‘£π‘š+1, 𝑣2,π‘š+1, 𝑣2,1, 𝑣2,2. 

Certainly 𝑣1,1 should be colored by the color which used at the cut vertices, beside color 
1, π‘š + 1 and 2. Suppose that 𝑣1,1 being color with π‘˜. It’s impacted there is no rainbow 
vertex path between vertex  π‘£π‘˜,2 and 𝑣𝑖,2 for 𝑖 β‰  π‘˜. So that, graph 𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,𝑗 ) cannot be 

colored with π‘š + 1 colors, so we obtain 

π‘Ÿπ‘£π‘ (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,𝑗 )) β‰₯ π‘š + 2    (5) 

In order to proof π‘Ÿπ‘£π‘ (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,𝑗 )) ≀ π‘š + 2, define a vertex-coloring 

𝛽: 𝑉 (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,𝑗 )) β†’ [1, π‘š + 2] as follows. 

𝛽(π‘£π‘š+1) = π‘š + 2 
𝛽(𝑣𝑖,𝑗 ) = (𝑖 + 𝑗)π‘šπ‘œπ‘‘(π‘š + 1), 𝑖 ∈ [1, π‘š], 𝑗 ∈ [1, π‘š + 1] 

We are able to find a rainbow path for every pair vertices 𝑒 and 𝑣 in 𝑉 (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,𝑗 )) as 

shown in table 2. 

Tabel 2. The rainbow vertex 𝑒 βˆ’ 𝑣 path for graph 𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,𝑗 ) 

𝒖 𝒗 Condition Rainbow-vertex path 
𝑒 is adjacent to v Trivial 
π’—π’Š,𝒋 π’—π’Œ,𝒍 π’Š, π’Œ ∈ [𝟏, π’Ž] 

𝒋, 𝒍 ∈ [𝟏, π’Ž + 𝟏] 
π’Œ β‰  π’Š + 𝒍, π’Œ β‰  π’Š βˆ’ 𝒍, π’Œ

∈ [𝟐, π’Ž βˆ’ 𝟏] 
If π’Š = 𝟏, π’Œ β‰  π’Ž 
others 

𝒖, π’—π’Š,𝒋+𝟏, π’—π’Š,𝒋+𝟐, … , π’—π’Š,π’Ž+𝟏, π‘£π’Ž+𝟏,π’—π’Œ,π’Ž+𝟏, π’—π’Œ,𝟏, 𝒗 

 
 
 

𝒖, π’—π’Š,𝟏 , π’—π’Š,π’Ž+𝟏, π’—π’Ž+𝟏,π’—π’Œ,π’Ž+𝟏, π’—π’Œ,𝟏, 𝒗 

 
So we conclude that 



The Rainbow Vertex-Connection Number of Star Fan Graphs  

Ariestha Widyastuty Bustan 116 

π‘Ÿπ‘£π‘ (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,𝑗 )) ≀ π‘š + 2     (6) 

From equation (5) and (6), we have π‘Ÿπ‘£π‘ (𝑆(π‘š, 𝐹𝑛 , 𝑣𝑖,𝑗 )) = π‘š + 2 

 
Figure 4. 𝑆(6, 𝐹6, 𝑣𝑖,7) 

 
 

REFERENCES 

 

[1]  R. Diestel, Graph Theory 4th Edition, Springer, 2010. 

[2]  M. Krivelevich and R. Yuster, "The rainbow connection of a graph is (at reciprocal to 
its minimum degree," Journal of Graph Theory, Vol. 63, no. 2, pp 185-191, 2010. 

[3]  X. Li and S. Liu, "Rainbow vertex-connection number of 2-connected graphs," ArXiv 
preprint arXiv: 1110.5770, 2011. 

[4]  D. N. Simamora and A. N. M. Salman, "The rainbow (vertex) connection number of 
pencil graphs," Procedia Computer Science, vol. 74, pp 138-142, 2015. 

[5]  A. W. Bustan, " Bilangan terhubung titik pelangi untuk graf lingkaran bintang 
(SmCn)," Barekeng: Jurnal Ilmu Matematika dan Terapan, vol. 10, no. 2, pp. 77-81, 
2016.