Open Problem-2_Open Neighborhood Graphs

[Belmannu Devadas Acharya]

Dear All,

Given a finite $(p,q)$-graph $G=(V,E)$, I had defined its open neighborhood graph, denoted $N(G)$, way back in the year 1972 as the graph with vertex-set $V(N(G))=V$ and two vertices $u$ and $v$ adjacent in $N(G)$ whenever $N(u) \cap N(v) \ne \emptyset$, where for any vertex $x$ of $G$,  $N(x)$ denotes the set of vertices that are adjacent to $x$ (or the so-called 'neighbors' of $x$). 

It was subsequently pointed out by F. Escalante et al. (see the attached paper) that $N(G)$ is precisely the $2$-path graph $(G)_2$ of $G$.

In my Ph.D. thesis, I had obtained a characterization of graphs $G$ for which $N(G)$ is isomorphic to the standard line graph $L(G)$ of $G$. However, as of this date, I am not satisfied with its elaborate statement. It is highly desirable to have a neat (and possibly a computationally 'good') characterization.  

Further, there is a 'line version' of the concept. Define the open line-neighborhood graph of a given graph $G$, denoted $N_e(G)$, of $G$ defined by taking for its vertex-set the the family of open edge-neighborhoods $N_e(xy)$, for $xy \in E$, and defining two vertices of $N_e(G)$ adjacent whenever $N_e(uv) \cap N_e(xy) \ne \emptyset$, where $N_e(xy)$ is the set of all edges in $G$ that intersect the set $\{x,y\}$. Note that $N_e(G)$ and $L(G)$ are not necessarily isomorphic. Hence, it would be interesting to study open line-neighborhood graphs, viz., graphs $H$ for which there exist graphs $G$ such that $H$ is isomorphic to $N_e(G)$. I had posed this problem too, vide Graph Theory Newsletter, 1973.  I am not aware of anyone who considered this problem. But, with the current knowledge on intersection graphs it should make an interesting study. 

I wish you all good luck.

B.D. ACHARYA