Definition of Perfect Elimination Ordering?

Question

The answer to this question could be trivial !

Definition:

According to the wikipedia page:

A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each vertex $v$, $v$ and the neighbors of $v$ that occur after $v$ in the order form a clique.

I'm not sure if I understand completely the definition .

Question?

Could somebody explain a little bit the definition, or give some example to illustrate the idea ? ( I have not understand the following sentence "that occur after $v$ in the order")

Any idea will be useful!

Answer 1

The sentence is a little difficult to unpack, but the idea is that:

1. The vertices in the graph have an ordering (or 'labels').
2. For each vertex ($v_i$), take the set (S) consisting of {$v_i$} $\cup N_j(v)$ where $Nj$ is the neighbours of v with position in the ordering > i
3. S is a clique

There is an algorithm for creating such an ordering called the maximum cardinality search, which is nice and simple. I found it here but I'm sure it's described in various places.

There are also a couple of examples in this question:

https://cs.stackexchange.com/questions/10438/what-is-the-maximum-number-of-shortest-paths-between-any-pair-of-vertices-in-a-c