2
$\begingroup$

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 ...

$\endgroup$
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.