# Existence of neighborhood inclusion for 4-chordal graphs

Let $N(v)$ be the (open) neighbourhood set of a vertex $v$, and let $N[v]$ be the closed neighbourhood set of $v$.

A graph $G$ is called 4-chordal if $G$ has no induced cycle with five or more vertices.

Question: Does every 4-chordal graph $G$ have two vertices $x$ and $y$ such that $N(x)$ is a subset of $N(y)$ or $N[x]$ is a subset of $N[y]$?

I think the answer is yes, but didn't find a proof so far.

The answer is yes for chordal graphs due to simplicial vertices.

But for 4-chordal graphs, I did not see any result in this direction. There are generalizations of simplicial vertices of $k$-chordal graphs due to Krithika, Mathew, Narayanaswamy and Sadagopan (2013) and Chavatal, Rusu and Sritharan (2002), but these notions of simplicial vertices do not answer the question as far as I see ...

## 1 Answer

The answer is no. A counterexample is the triangular prism graph. Up to symmetry, there is a unique 5-cycle and a unique 6-cycle in the triangular prism and both these cycles have chords. Hence the triangular prism is 4-chordal. On the other hand, it is also easy to see that no (closed) neighbourhood is contained in any other (closed) neighbourhood.

• I think you mean "Up to symmetry" rather than "By symmetry". – verret Sep 20 '14 at 16:40
• Thank you very much for your counterexample. It saves quite a lot of time for me... – Turker Biyikoglu Sep 22 '14 at 12:25