2017/10/01 by Johan Kok, Sudev Naduvath, Kok, Johan +3
Computer Science · Mathematics · #05C15 #05C38 #05C75 #05C85 #Advanced Graph Theory Research #FOS: Mathematics #General Mathematics (math.GM) #Graph theory and applications #Limits and Structures in Graph Theory #math.GM #msc:05C15 #msc:05C38 #msc:05C75 #msc:05C85
paper · pdf · doi:10.48550/arxiv.1710.00383
8 pages
arxiv created 2017/10/01 · openalex publication_date 2017/10/01 · arxiv updated 2017/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A rainbow neighbourhood of a graph G with respect to a proper colouring \C of G is the closed neighbourhood N[v] of a vertex v in G such that N[v] consists of vertices from all colour classes in G with respect to \C. The number of vertices in G which yield a rainbow neighbourhood of G is called its rainbow neighbourhood number. In this paper, we show that all results known so far about the rainbow neighbourhood number of a graph G implicitly refer to a minimum number of vertices which yield rainbow neighbourhoods in respect of the minimum proper colouring where the colours are allocated in accordance with the rainbow neighbourhood convention. Relaxing the aforesaid convention allows for determining a maximum rainbow neighbourhood number of a graph G. We also establish the fact that the minimum and maximum rainbow neighbourhood numbers are respectively, unique and therefore a constant for a given graph.