Unveiling rainbow connections in extended sandat graphs

Abstract

Graph theory is a fundamental area of discrete mathematics, with graph colouring being one of its most captivating topics. In particular, edge colouring involves assigning colours to the edges of a graph, ensuring that no two adjacent edges have the same colour while using the fewest possible colours. A rainbow path in an edge-coloured graph is one where no two edges in the path have the same colour. If every pair of vertices in a graph is connected by at least one rainbow path, the graph is rainbow-connected. The minimum number of colours needed for a graph to be rainbow-connected is called the rainbow connection number (𝑟𝑐(𝐺)). Map colouring, optimizing timetables, solving Sudoku puzzles, and minimum cost are some examples of the applications of graph colouring. Hence, it is important to study and introduce new graph classes. The present study introduced the comb product of the operation of cycle graph 𝐶𝑛 and the higher-order extended version of the Sandat graph 𝑆𝑆𝑡𝑚(𝑛). The comb product of 𝐶4 and 𝑆𝑆𝑡𝑚(𝑛) has been explored in detail. This comb product can be illustrated by connecting each vertex of 𝐶4 to 𝑆𝑆𝑡𝑚(𝑛) such that the vertex set 𝑉(𝐶4 ⊳𝑆𝑆𝑡𝑚(𝑛))= {𝑟𝑘,𝑠𝑖𝑗ℎ ,𝑡𝑖∶1≤𝑘≤4,1≤𝑖≤𝑛,1≤𝑗≤2 ,1≤ℎ≤𝑚+1} and the edge set 𝐸(𝐶4 ⊳𝑆𝑆𝑡𝑚(𝑛))={𝑟1𝑟2 ,𝑟2𝑟3,𝑟3𝑟4,𝑟4𝑟1} ∪ {𝑟𝑡𝑖 ,𝑟𝑠𝑖𝑗ℎ ,𝑡𝑖𝑠𝑖𝑗1 ,𝑠𝑖𝑗𝑝𝑠𝑖𝑗𝑝+1∶ 1≤𝑖≤𝑛,1≤𝑗≤2,1≤ℎ≤𝑚+1,1≤𝑝≤𝑚}. An algorithm has been proposed for rainbow colouring of this graph aiming to establish the rainbow connection number. Future works will be conducted to confirm this rainbow connection number and introduce the comb product of the non-symmetric higher-order extended Sandat graphs. The rainbow connection number has practical applications in network design, such as in secure data transmission, where diverse routing paths help prevent interception and ensure reliability.