## 6 LexBFS, a Special Case  
Algorithm LexBFS, with respect to the properties discussed so far, exhibits stronger properties than any other algorithm of the MLS family (as far as we know). In fact, LexBFS, run on a _non-chordal_ graph, has the properties which are those of MLS (with a total order) run on a _chordal graph_:  
Figure 7: MNS on a non-chordal graph does not end on an OCF-vertex: the substars of \(1\) are \(\{3,8\}\) and \(\{2,8\}\), but there is no edge \(23\). 1. Vertex \(\alpha(1)\) belongs to a complex, and the vertices of this moplex have consecutive numbers. 2. The minimal separators included in the neighborhood of vertex 1 are totally ordered by inclusion. Moreover, LexBFS refines the numbering of the slices: LexBFS numbers the components of \(G(V-N(\alpha(1))\) one by one, instead of numbering the slices (which are groups of components) one by one. As we will see, we will thus partition the slices into _thin slices_. The following result is shown in [13] see their Theorem 5.1 and their Property 5.5):  
**Theorem 6.1**: _[_13_]_ _In an arbitrary graph, the vertex numbered 1 by LexBFS belongs to a moplex whose vertices are numbered consecutively._  
**Example 6.2**: _Figure 8 shows an execution of LexBFS on a non-chordal graph \(G\). The moplex containing \(\alpha(1)\) is \(X_{1}=\{1,2\}\)._  
Let us now consider an execution of LexBFS on an arbitrary graph \(G\), let \(X_{1}\) be the moplex containing vertex \(\alpha(1)\). We will define the thin slices of the execution in a similar fashion to the slices (see Notations 4.3):  
**Notations 6.3**: _For any graph \(G=(V,E)\) and any LexBFS ordering \(\alpha\) on \(V\), with \(X_{1}\) the moplex containing vertex \(\alpha(1)\),_  
* \(a\) component__\(C_{i}\) _is a connected component of_ \(G(V-N(X_{1}))\)_, with_ \(k\) _the number of such components._
* \((C_{1},C_{2},...,C_{k})\) _denotes the sequence of the components ordered as follows:_ \(\forall i\in[1,k-1]\)_,_ \(\alpha^{-1}(y_{i})>\alpha^{-1}(y_{i+1})\)_, where_ \(y_{i}\) _denotes the vertex of_ \(C_{i}\) _with maximum number (_\(\alpha^{-1}(y_{i})=max\{\alpha^{-1}(y),y\in C_{i}\}\)_)._
* _the thin slices are the subsets_ \(F_{1}\)_,_ \(F_{2}\)_,...,_ \(F_{k}\) _of_ \(V\) _partitioning_ \(V\) _as follows:_ \(\forall i\in[1,k]\)_,_ \(F_{i}=C_{i}\cup S_{i}\)_, where_ \(S_{i}=N(C_{i})-(\cup_{1\leq j<i}N(C_{j}))=N(C_{i})-(\cup_{1\leq j<i}S_{j})\)_, and_ \(t_{i}\) _denotes the vertex of_ \(F_{i}\) _with maximum number._ _We say that_ \(\alpha\) _numbers the thin slices in increasing order if it numbers the vertices of_ \(F_{1}\) _first (with the largest numbers), then the vertices of_ \(F_{2}\) _etc., i.e. if_ \(\forall i\in[1,k-1]\)_,_ \(\forall t\in F_{i}\)_,_ \(\alpha^{-1}(t)>\alpha^{-1}(t_{i+1})\)_._  
**Example 6.4**: _Figure 9 shows the thin slices defined by the LexBFS execution on a non-chordal graph from Figure 8. The thin slices are: \(\{10,9,8,7\},\{6\},\{5,4,3\}\) and \(\{2,1\}=X_{1}\)._  
We will use the following two lemmas from [13]:  
**Lemma 6.5**: _No vertex of \(V-C_{1}\cup N(C_{1})\) can be numbered before all the vertices of \(C_{1}\cup N(C_{1})\) are numbered._  
**Lemma 6.6**: _When LexBFS starts numbering \(V-(C_{1}\cup N(C_{1}))\), every unnumbered vertex has exactly the same label._  
**Theorem 6.10**: _For any graph \(G\) (chordal or not) and any LexBFS ordering \(\alpha\) of \(G\), the minimal separators of \(G\) included in \(N(\alpha(1))\) are totally ordered by inclusion._  
Proof:Let \(C_{1},C_{2},...,C_{k}\) be as above the connected components of \(G(V-X_{1}\cup N(X_{1})\) (where \(X_{1}\) is the complex containing vertex \(\alpha(1)\)). We claim that \(N(C_{1})\subseteq N(C_{2})\subseteq...\subseteq N(C_{k})\). Suppose by contradiction that there are two components \(C_{i}\) and \(C_{j}\), \(i<j\), such that \(N(C_{i})\
ot\subseteq N(C_{j})\), and let \(y\) be in \(N(C_{i})-N(C_{j})\).