Graphs with special neighbourhood orderings of vertices (Q1309442)

For a simple graph \(G\) let \(d(x,z)\) be the length of a shortest path connecting \(x\) and \(z\) in \(G\). Let \(N^ i(x)=\{z\in V(G): d(x,z)=i\}\), \(i=1,2\), and \(N^ 3(x)=\{z\in V(G): d(x,z)\in \{1,2\}\}\). Write \(x\prec_ i y\) iff \(N^ i(x)\subseteq N^ i(y)\cup\{y\}\). It is proved that no graph \(G\) can contain a subset \(\{v_ 1,\dots,v_ n\}\subseteq V(G)\), \(3\leq n\leq | V(G)|\), such that \(v_ j\succ_ i v_{j+1}\) and \(v_{j+1}\not\succ_ i v_ j\), \(j=1,\dots,n\) and \(i=1\) and 3. On the other hand, in the case \(i=2\) there exists an infinite family of such graphs. Finally, a relation to cotolerance graphs is discussed.