On Middle Neighborhood Graphs

Abstract

The middle neighborhood graph ${M_{nd}(G)}$ of a graph $G = (V, E)$ is the graph with the vertex set ${V}\cup{S}$ where { S } is the set of all open neighborhood sets of { G }in which two vertices u and v are adjacent if $u, v\in S$ and $u\cap v\neq\phi$ or $u\in V$ and v is an open neighborhood set of G containing u. In this paper, some properties of this new graph are established. Also characterizations are given for graphs (i) whose middle neighborhood graphs are connected, (ii) whose middle neighborhood graphs are Eulerian.