Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$\mathcal G_n $ conists of graphs $G$ on $n$ vertices $1,\ldots,n$ such that for all $i<j$, each vertex $k, i<k<j$ is not adjacent to at least one of $i$ and $j$.

Question 1. Can we classify $\mathcal G_n$?

Question 2. Is there any nice family of graph which is a subclass of $\mathcal G_n$? (Seems like path $P_n$, star $S_n$ and probably trees on $n$ vertices are in $\mathcal G_n$) I will appreciate any comments for at least question 2.

share|cite|improve this question

Your condition could be summed up like this:

  • There exists a permutation of vertices (namely $1,2,\ldots,n$) such that for any $v \in V$ all its neighbors are on the left, or all its neighbors are on the right.

This implies that the graph is bipartite. Now, take any bipartite graph and put all vertices from one side at $1,2,\ldots,|V_1|$ and the other at $n-|V_2|+1,\ldots,n$. Clearly this graph satisfies your condition, hence, your class is the class of bipartite graphs.

I hope this helps ;-)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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