# A class of graphs

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

-

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