Some Results on Neighbourhood Highly Irregular Graphs

Abstract

Let \(G = (V, E)\) be a finite simple connected graph. For any vertex \(v\) in \(V\), let \(N_G(v) = \{u \in V: uv \in E\}\) be the open neighbourhood of \(v\), and let \(N_G[v] = N_G(v) \cup \{v\}\) be the closed neighbourhood of \(v\). A connected graph \(G\) is said to be neighbourhood highly irregular (or simply NHI) if for any vertex \(v \in V\), any two distinct vertices in the open neighbourhood of \(v\) have distinct closed neighbourhood sets. In this paper, we give a necessary and sufficient condition for a graph to be NHI. For any \(n \geq 1\), we obtain a lower bound for the order of regular NHI graphs and a sharp lower bound for the order of NHI graphs with clique number \(n\), which is better than the bound attained earlier.