The rainbow connection number of the extended version of the sandat graph

Abstract

Graph colouring is a fundamental problem in Graph Theory, with applications varying over diverse domains related to real-world applications such as channel assignment in cellular networks, scheduling and task assignment, and register allocation in computer optimisation. Graph colouring is a special case of graph labelling with assigning colours to edges or vertices of a graph. Assigning colours to each edge in a graph so that no two adjacent edges have the same colour with a given optimal number of colours is the edge colouring of a graph. In an edge-coloured graph, if there is a path with no two edges having the same colour, then that path is called a rainbow path. If every pair of vertices in a graph is connected by at least one rainbow path, then that graph is called a rainbow-connected graph. The minimum number of colours used in a rainbow-connected graph is the rainbow connection number 𝑟(𝐺) of that graph. The Sandat graph on 3𝑛 + 1 vertices, denoted by 𝑆t(𝑛), is a graph with the vertex set 𝑉(𝑆t(𝑛)) = {𝑟, 𝑠ᵢⱼ,𝑡𝑖|1 ≤ 𝑖 ≤ 𝑛 and1 ≤ 𝑗 ≤ 2} and the edge set 𝐸(𝑆t(𝑛)) = (𝑟𝑡ᵢ, 𝑟𝑠𝑖, 𝑠𝑖ⱼ𝑡𝑖 |1 ≤ 𝑖 ≤ 𝑛 and 1 ≤ 𝑗 ≤ 2). In this study, an extended version of the Sandat graph 𝑆s𝑡ₘ(𝑛) having 𝑛𝑛 number of petals was obtained using the symmetrical subdivisions of having 2(2 + 𝑚); 𝑚 ∈ {1,2,3, … } vertices for each petal and with the vertex set 𝑉𝑉(𝑆𝑆𝑡𝑚(𝑛)) and the edge set 𝐸(𝑆𝑆𝑡𝑚(𝑛)) denoted by 𝑉(𝑆𝑆𝑡𝑚(𝑛)) = {𝑟𝑟, 𝑠𝑖 ℎ ,𝑡𝑖 ; 1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 2 , 1 ≤ ℎ ≤ 𝑚 + 1} and 𝐸(𝑆𝑆𝑡𝑚(𝑛)) = {𝑟𝑡𝑖 , rsᵢʰⱼ ,𝑡𝑖𝑠𝑖¹,sᵢᵏⱼsᵢᵏⱼ⁺¹ ; 1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 2, 1 ≤ ℎ ≤ 𝑚 + 1, 1 ≤ 𝑘 ≤ 𝑚}. The rainbow connection number of the extended version of the Sandat graph 𝑆𝑆𝑡𝑚(𝑛) having 𝑛 number of petals is three when 𝑛𝑛 ≥ 2 was proved. Future study plans to introduce the non-symmetric extended version of the Sandat graph and the rainbow colouring of that graph