# Computing a Clique Tree with the Algorithm Maximal Label Search
## 5 Extended Results
### MLS on a Non-Chordal Graph  
A MLS ordering of a non-chordal graph \(G\) is not necessarily an MEO of \(G\). It was shown in [8] that LexBFS ends on a moplex, i.e., if \(\alpha\) is a LexBFS ordering of a non-clique graph \(G\), then there is a moplex \(X_{1}\) of \(G\) such that \(X_{1}=\{\alpha(1),\ldots,\alpha(|X_{1}|)\}\). As the restriction of \(\alpha\) to \(V\setminus X_{1}\) is a LexBFS ordering of \(G(V\setminus X_{1})\), it follows that \(\alpha\) is compatible with a simple moplex partition of \(G\). However, if \(G\) is not chordal, then \(\alpha\) is not necessarily a PMO of \(G\), and it is not necessarily an MMO of \(G\) and not even an MEO of \(G\). **Example 4**: _Let \(G\) be the graph shown in Figure 4, and let \(\alpha=(1,2,3,4,5)\). \(\alpha\) is a LexBFS ordering of \(G\) (the final labels are indicated). \(\alpha\) is compatible with the simple moplex partition \((\{1\},\{2,3\},\{4,5\})\). However, \(\alpha\) is not an MEO of \(G\) since the graph \(H=G_{\alpha}^{+}\) (shown in the figure with dashed fill edges) is not a minimal triangulation of \(G\)._  
The work from [8] also showed that if \(\alpha\) is a LexBFS ordering of a graph \(G\), then the minimal separators included in \(N(\alpha(1))\) are totally ordered by inclusion and that \(\alpha\) consecutively numbers the vertices of each connected component of \(G(V\setminus N[\alpha(1)])\) and its neighborhood. More accurately, there is an order \((C_{1},\ldots,C_{p})\) on the connected component of \(G(V\setminus N[\alpha(1)])\), such that for each \(i\) in \([1,p-1]\); \(N(C_{i})\subseteq N(C_{i+1})\) (the minimal separators included in \(N(\alpha(1))\) are the sets \(N(C_{i})\)), and \(\alpha\) is compatible with the ordered partition \((X_{1},N[C_{p}]\setminus N(C_{p-1}),\ldots,N[C_{2}]\setminus N(C_{1}),N[C_{1}])\), where \(X_{1}\) is the moplex containing \(\alpha(1)\). [PERSON] et al. [14] showed that LexDFS also ends on a moplex of the input graph \(G\) (and therefore, a LexDFS ordering is compatible with a simple moplex partition of \(G\)), but they left open the question whether LexDFS orderings also have the properties on minimal separators and connected components. The following counterexample shows that these properties of LexBFS do not extend to LexDFS. **Counterexample 2**: _Let \(G\) be the graph shown in Figure 5, and let \(\alpha=(1,2,\ldots,7)\). \(\alpha\) is a LexDFS ordering of \(G\) (the final labels are indicated). The minimal separators included in \(N[1]\) are \(\{2,6\}\) and \(\{4,6\}\) and are incomparable for inclusion. If the property on connected components was true, \(C_{1}\) would be the component numbered last by \(\alpha\), i.e., \(\{7\}\), but the vertices of \(N[\{7\}]\) (\(7\), \(6\) and \(2\)) are not numbered consecutively by \(\alpha\). If \(G\) is the graph shown in Figure 6 with \(\alpha=(1,2,\ldots,6)\), even the restriction of \(\alpha\) to \(V\setminus N[1]\) is not compatible with a sequence of the connected components of \(G(V\setminus N[1])\)._  
Figure 4: Lexicographic Breadth-First Search (LexBFS) on a non-chordal graph computes an ordering that is compatible with a simple moplex partition, but not with an MEO. It is shown in [12] that for each labeling structure \(\mathcal{L}\) with a total order on labels and each \(\mathcal{L}\)-MLS ordering \(\alpha\) of a graph \(G\), \(\alpha(1)\) is an OCF-vertex of \(G\), i.e., satisfies the property: for each pair \(\{y,z\}\) of non-adjacent vertices in \(N(\alpha(1))\), there is a connected component \(C\) of \(G(V\setminus N[\alpha(1)])\) such that \(y,z\in N_{G}(C)\). However, the definition of a labeling structure given in [12] is less general than the definition given in this paper, as IC is replaced by conditions (p1): \(l\prec Inc(l,i)\) and (p2): \(if\ l\prec l^{\prime}\)_then_\(Inc(l,i)l\prec Inc(l^{\prime},i)\): (p1) and (p2) imply IC and IC implies (p1), but does not imply (p2).