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\ge 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.