Is it possible to construct a unit interval graph with $n$ vertices and clique number $k$ such that any other unit interval graph with same number of vertices and clique number is a sub-graph of that graph or isomorphic to a sub-graph of that graph?

My construction for k=3 is, Unit interval graph for n=8 and k=3 However, i could not generalize my proof. Please help.

  • 1
    $\begingroup$ The graph is simply the $(k-1)$th power of the path on $n$ vertices, $P_n^{k-1}$. $\endgroup$ – Andrew D. King Jun 17 '14 at 23:28

Your Answer

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

Browse other questions tagged or ask your own question.