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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .