Rainbow Vertex Connection Number of Broom Graph, Triangular Book Graph and Triangular Book with Bookmark

Rainbow Vertex Connection Number of Broom Graph, Triangular Book Graph and Triangular Book with Bookmark

V. Jothika¹, P. Mythili^2*

¹PG student, Department of Mathematics, Kaamadhenu Arts and Science College, Sathyamangalam, Erode, Tamil Nadu, India.

²Assistant Professor, Department of Mathematics, Kaamadhenu Arts and Science College, Sathyamangalam, Erode, Tamil Nadu, India.

*Corresponding author

DOI: https://doi.org/10.51584/IJRIAS.2025.1005000106

Received: 13 May 2025; Accepted: 19 May 2025; Published: 19 June 2025

ABSTRACT

The Rainbow Vertex Connection Number of a graph is the minimum number of colors required to make a graph rainbow vertex connected. A graph is said to be a rainbow vertex connected if there exists a rainbow vertex path between every pair of distinct vertices. In this paper the rvc(G) of broom graph, triangular book graph and triangular book with bookmark is found.

Keywords: Rainbow vertex connection number, Broom graph, Triangular book graph, Triangular book with bookmark.

INTRODUCTION

Only simple, non-trivial and connected graphs are taken into account. Some authors consider rainbow connectivity to be a measurement of a graph’s connection. The connected graphs rainbow vertex connection number is rvc(G)diam(G)-1.

N.M. Subakti, D.R. Silaban and K.A. Sugeng [4] discovered the rainbow connection number of the sun graph and path graph. Irvania Sukma Kumala, A.N.M.Salman [2] calculated the rainbow connection number of flower graph () and () flower graph. W.D.D.P. Dewananda and K.K.K.R. Perera [1] found out the rainbow vertex connection number of ladder graph and roach graph.

The formula for the rainbow vertex connection number of broom graph, triangular book graph and triangular book with bookmark is derived in this study.         

Preliminaries      

Definition 2.1

A broom graph  is a graph with n vertices consisting of a path P with m vertices and (n-m) pendant vertices.

Fig 1: Broom graph

Definition 2.2

The triangular book with n-pages consists of n copies of the cycle C3 that shares a mutual edge referred to as the spine or base of the book. This graph is represented as B (3, n). In simpler terms it is the complete tripartite graph k1, 1, n.

Fig 2: Triangular book graph

Definition 2.3

The triangular book with bookmark is a triangular book B (3, n) with a pendant edge attached at any one of the end vertices of the spine. This graph is denoted by T  (u, v) (v, w).

Fig 3: Triangular book with bookmark

THEOREMS

Theorem 3.1

Let  be the broom graph. The rainbow vertex connection number is rvc() = m-1, nm.

Proof:

Case 1:

When both n and m are odd. Let n=5, m=3. It has (n-m) pendant vertices. That is it has  5-3=2 pendant vertices. In figure 4. We consider path to  has diameter 3. Here and  has common color and the internal vertices between it are distinct. As ‘V’ vertices are pendant, the same color can be given to all the vertices of ‘V’. Then rvc(G)  diam(G)-1. rvc(G)  3-1. rvc(G)= 2. Thus rvc() is obtained by m-1.

Fig 4: Rainbow vertex connection number of Broom graph

Case 2:

When both n and m are even. Let n=4, m=2. It has (n-m) pendant vertices. That is it has 4-2=2 pendant vertices. In figure 5. We consider path to  has diameter 2. Here and  has a common color and the internal vertices between it are distinct. As ‘V’ vertices are pendant, the same color can be given to all the vertices of ‘V’. Then rvc(G)  diam(G)-1. rvc(G)  2-1. rvc(G) =1. Thus rvc() is obtained by m-1.

Fig 5: Rainbow vertex connection number of Broom graph

Case 3:

When n is odd and m is even. Let n=5, m=2. It has (n-m) pendant vertices. That is it has 5-2=3 pendant vertices. In figure 6. We consider path to  has diameter 2. Here and  has a common color and the internal vertices between it are distinct. As ‘V’ vertices are pendant, the same color can be given to all the vertices of ‘V’. Then rvc(G)  diam(G)-1. rvc(G)  2-1. rvc(G) =1. Thus rvc() is obtained by m-1.

Fig 6: Rainbow vertex connection number of Broom graph

Case 4:

When n is even and m is odd. Let n=6, m=3. It has (n-m) pendant vertices. That is it has 6-3=3 pendant vertices. In figure 7. We consider path to  has diameter 3. Here and  has a common color and the internal vertices between it are distinct. As ‘V’ vertices are pendant, the same color can be given to all the vertices of ‘V’. Then rvc(G)  diam(G)-1. rvc(G)  3-1. rvc(G)= 2. Thus rvc() is obtained by m-1.

Fig 7: Rainbow vertex connection number of Broom graph

Theorem 3.2

The triangular book graph B (3, n) has rvc(B (3, n))=1.

Proof:

Case 1:

When n is odd. Let n=3. In figure 8. Consider a path u and v that has diameter 2. Here  is the internal vertex and the color is assigned. Then rvc(G)  diam(G)-1. rvc(G)  2-1. rvc(G)= 1. Thus rvc(B (3, n)) is 1.

Fig 8: Rainbow vertex connection number of Triangular book graph B (3, 3)

Case 2:

When n is even. Let n=4. In figure 9.  Consider a path u and v that has diameter 2. Here  is the internal vertex and the color is assigned. Then rvc(G)  diam(G)-1. rvc(G)  2-1. rvc(G)= 1. Thus rvc(B (3, n)) is 1.

Fig 9: Rainbow vertex connection number of Triangular book graph B (3, 4)

Theorem 3.3

The triangular book with bookmark T  (u, v) (v, w) has rvc(T (u, v) (v, w))=1.

Proof:

Case 1 :

When n is odd. Let n=5. In figure 10. Consider a path u and v that has diameter 2. Here  is the internal vertex and the color is assigned. Then rvc(G)  diam(G)-1. rvc(G)  2-1. rvc(G)= 1. Thus rvc(T (u, v) (v, w)) is 1.

Fig 10: Rainbow vertex connection number of Triangular book with bookmark T  (u, v) (v,w)

Case 2:

When n is even. Let n=4. In figure 11. Consider a path u and v that has diameter 2. Here  is the internal vertex and the color is assigned. Then rvc(G)  diam(G) -1. rvc(G)  2-1. rvc(G)= 1. Thus rvc(T (u, v) (v, w)) is 1.

Fig 11: Rainbow vertex connection number of Triangular book with bookmark T  (u, v)  (v, w)

CONCLUSION

The formula for the rainbow vertex connection number of broom graph, triangular book graph and triangular book with bookmark has been found.

REFERENCES

1. W.D.D.P. Dewananda and K.K.K.R. Perera, The Rainbow Vertex Connection Number of Ladder graphs and Roach graphs, Ceylon Journal of Science 52(3) 2023:305-308.
2. Irvania Sukma Kumala, A.N.M. Salman, The Rainbow Connection Number of a Flower (,graph and Flower (,) graph, Procedia Computer Science 74(2015) 168-172.
3. P. Mythili and S. Gokilamani, Total Coloring of Comb Related Graphs and Umbrella Graph, International Journal of Creative Research Thoughts (IJCRT), May 2022, ISSN: 2320-2882.
4. N.M. Surbakti, D.R. Silaban and K.A. Sugeng, The Rainbow Connection Number of graph resulting in the operation of Sun Graph and Path Graph, AIP Conference Proceedings 2234 030010(2020).