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.