On the traversability of near common neighborhood graph of a graph

Abstract

The near common neighborhood graph of a graph G, denoted by ncn(G) is defined as the graph on the same vertices of G, two vertices are adjacent in ncn(G), if there is at least one vertex in G not adjacent to both the vertices. In this research paper, the conditions for ncn(G) to be disconnected are discussed and also we present characterization for graph ncn(G) to be hamiltonian and eulerian.

Keywords

• near common neighborhood graph
• hamiltonian graph
• eulerian graph