Abstract

A rainbow neighborhood of a graph Г is defined as the closed neighborhood N [v] of a vertex v ∈ V (Г) that contains at least one vertex of every color present in a given proper chromatic coloring C of Г. The total number of vertices in Г whose closed neighborhoods form rainbow neighborhoods is termed the rainbow neighborhood number of Г, denoted by rχ(Г). In this study, the authors introduce a new class of graphs, called Shiju-graphs, which are subgraphs of the strong product of two paths. Also, explore and analyze various properties of these graphs, including their chromatic number, rainbow neighborhood number, and several other related graph parameters.

Keywords

Color Class, Rainbow Neighborhood, Rainbow Neighborhood Number, Shiju Graphs.

References

[1] F. Harary, “Graph Theory Narosa Publishing House Reading,” New Delhi, 1988.
[Google Scholar]

[2] J.A. Bondy, and U.S.R. Murty, Graph Theory with Applications, Macmillan London, vol. 290, 1976.
[Google Scholar] [Publisher Link]

[3] Douglas B. West, Introduction to Graph Theory, 2001.
[Google Scholar] [Publisher Link] 

[4] Gary Chartrand, and Ping Zhang, Chromatic Graph Theory, Chapman and Hall/CRC, 2019.
[CrossRef] [Google Scholar] [Publisher Link] 

[5] Tommy R. Jensen, and Bjarne Toft, Graph Coloring Problems, John Wiley & Sons, 2011.
[Google Scholar] [Publisher Link]  

[6] A.B. Kempe, “On the Geographical Problem of the Four Colours,” American Journal of Mathematics, vol. 2, no. 3, pp. 193-200, 1879.
[CrossRef] [Google Scholar] [Publisher Link] 

[7] Johan Kok, and Sudev Naduvath, “On the Rainbow Neighbourhood Number of Set-Graphs,” arXiv preprint arXiv:1712.02324, pp. 1-7, 2017.
[CrossRef] [Google Scholar] [Publisher Link] 

[8] Sudev Naduvath et al., “Some New Results on the Rainbow Neighbourhood Number of Graphs,” National Academy Science Letters, vol. 42, no. 3, pp. 249-252, 2019.
[CrossRef] [Google Scholar] [Publisher Link]  

[9] Johan Kok et al., “A Note on the Rainbow Neighbourhood Number of Certain Graph Classes,” National Academy Science Letters, vol. 42, no. 2, pp. 135-138, 2019.
[CrossRef] [Google Scholar] [Publisher Link]   

[10] Johan Kok et al., “Rainbow Neighbourhood Number of Graphs,” Proyecciones (Antofagasta), vol. 38, no. 3, pp. 469-484, 2019.
[CrossRef] [Google Scholar] [Publisher Link]