## 7 The Orderings Defined by MLS and MLSM  
As explained above, MLS computes a peo of any chordal graph, and MLSM computes a meo of any graph. We can strengthen these properties to _moplex orderings_, introduced by [17]. We define a moplex to be simplicial if all its vertices are simplicial. We define a simplicial complex elimination scheme in a chordal graph by repeatedly choosing a moplex of the current graph, which is simplicial since the graph is chordal, and removing it, until the graph is a clique. If the graph is not chordal, we define the moplex elimination game in the same way as the simplicial elimination game: we simulate a moplex elimination scheme by repeatedly choosing a moplex of the current graph, adding every edge whose absence violates the simpliciality of this moplex, and removing it, until the graph is a clique. Thus we obtain an ordered partition \((X_{1},X_{2},...,X_{k})\) where \(X_{i}\) is a moplex of the current graph at step \(i\) if \(i<k\) and \(X_{k}\) is the final clique. A _moplex ordering_ is an ordering \(\alpha\) on \(V\) that numbers (from 1 to \(n\)) the sets \(X_{i}\) of such an ordered partition in increasing order, _i.e._ such that \(\forall i\in[1,k-1]\), \(\forall x\in X_{i}\), \(\forall x^{\prime}\in X_{i+1}\), \(\alpha^{-1}(x)<\alpha^{-1}(x^{\prime})\). Then \(G_{\alpha}^{+}\) is exactly the graph obtained from \(G\) by adding all edges added in the moplex elimination game. Any LexBFS ordering of a chordal graph, and any Lex M ordering of any graph, defines a moplex ordering [17]. We extend these results to MLS and MLSM:  
Figure 9: The thin slices defined by the LexBFS execution on a non-chordal graph from Figure 8.  
**Theorem 7.1**:
* _For any chordal graph_ \(H\) _and any labeling structure_ \(\mathcal{L}\)_, if the order on labels is total, then any_ \(\mathcal{L}\)_-MLS ordering of_ \(H\) _defines a complex ordering._
* _For any graph_ \(G\) _and any labeling structure_ \(\mathcal{L}\)_, if the order on labels is total, then any_ \(\mathcal{L}\)_-MLSM ordering of_ \(G\) _defines a complex ordering._  
For any chordal graph \(G\) and any labeling structure \(\mathcal{L}\), if the order on labels is total then any \(\mathcal{L}\)-MLS ordering of \(G\) is a complex ordering of \(G\): we have only to point out that by Theorem 5.1, any \(\mathcal{L}\)-MLS ordering \(\alpha\) of a non-clique chordal graph \(G\) ends on a complex \(X\) of \(G\) and that the restriction of \(\alpha\) to the chordal subgraph \(G(V-X)\) is itself a \(\mathcal{L}\)-MLS ordering of this subgraph, and the proof follows by induction on \(|V|\). For any graph \(G\) and any labeling structure \(\mathcal{L}\), if the order on labels is total then any \(\mathcal{L}\)-MLSM ordering of \(G\) is a complex ordering of \(G\): let \(\alpha\) be a \(\mathcal{L}\)-MLSM ordering of \(G\). For any \(k\) from \(1\) to \(n\), let \(G^{k}_{\alpha}\) denote the current graph of the simplicial elimination game just before processing \(\alpha(k)\), let \(V^{k}_{\alpha}\) be its set of vertices, _i.e._\(V^{k}_{\alpha}=\{\alpha(k),...,\alpha(n)\}\), and \(\alpha_{k}\) be the restriction of \(\alpha\) to \(V^{k}_{\alpha}\). To prove that \(\alpha\) is a complex ordering of \(G\), it is sufficient to prove that for any \(k\) from \(1\) to \(n\) such that \(G^{k}_{\alpha}\) is not a clique, \(\alpha_{k}\) ends on a complex of \(G^{k}_{\alpha}\). Consider any \(k\), \(1\leq k\leq n\), such that \(G^{k}_{\alpha}\) is not a clique and let us show that \(\alpha_{k}\) ends on a complex of \(G^{k}_{\alpha}\). By Property 3.2\(\alpha\) is a \(\mathcal{L}\)-MLS ordering of \(G^{+}_{\alpha}\), so \(\alpha_{k}\) is a \(\mathcal{L}\)-MLS ordering of \(G^{+}_{\alpha}(V^{k}_{\alpha})\), which is equal to \((G^{k}_{\alpha})^{+}_{\alpha_{k}}\).