On the Fading Number of a Graph

Abstract

The closed neighbourhood $N[v]$ of a vertex $v$ of a graph $G$, consisting of at least one vertex from all colour classes with respect to a proper colouring of $G$, is called a rainbow neighbourhood in $G$. The minimum number of vertices and the maximum number of vertices which yield rainbow neighbourhoods with respect to a chromatic colouring of $G$ are called the minimum and maximum rainbow neighbourhood numbers, denoted by $r_{\chi }^{-}(G)$, $r_{\chi }^{+}(G)$ respectively. In this paper, by a colour, we mean a solid colour and by a transparent colour, we mean the fading of a solid colour. The fading numbers of a graph $G$, denoted by $f^{-}(G)$, $f^{+}(G)$ respectively, are the maximum number of vertices for which the colour may fade to transparent without a decrease in $r_{\chi }^{-}(G)$ and $r_{\chi }^{+}(G)$ respectively.

6 Pages