1
$\begingroup$

How can we create a kernel perfect orientation of a complete graph? A kernel of a graph is a set of vertices in a graph $G$, which absorbs other vertices, that is, has all the vertices in its complement have a directed edge towards it in an orientation of $G$. A kernel -perfect orientation of graph is an orientation of the graph in which each subgraph has a kernel.

A kernel in a complete graph consists of just a vertex as it has edges to every other vertex. But, if the tournament (orientation of the complete graph) is kernel perfect, then we should have every sub-clique to have a kernel. So, how do we orient the edges to obtain a kernel perfect tournament. Any hints? Thanks beforehand.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What is wrong with just enumerating the vertices and orienting all edges from the vertex with a smaller number to that with the larger one? $\endgroup$
    – fedja
    Commented Aug 23, 2020 at 20:20
  • $\begingroup$ @fedja well, thanks. Your comment solves the question. You could post as an answer $\endgroup$
    – vidyarthi
    Commented Aug 23, 2020 at 21:55

0

Reset to default

You must log in to answer this question.