Moplex orderings generated by the LexDFS algorithm

Let $G$ be a graph with vertex set $V$. A moplex of $G$ is both a clique and a module whose neighborhood is a minimal separator in $G$ or empty. A moplex ordering of $G$ is an ordered partition $(X_1,X_2,?,X_k)$ of $V$ for some integer $k$ into moplexes which are defined in the successive transitory elimination graphs, i.e., for $1?i?k?1$, $X_i$ is a moplex of the graph $G_i$ induced by ${\cup }_{j=i}^k{X}_j$ and $X_k$ induces a clique. In this paper we prove the terminal vertex by an execution of the lexicographical depth-first search (LexDFS for short) algorithm on $G$ belongs to a moplex whose vertices are numbered consecutively and further that the LexDFS algorithm on $G$ defines a moplex ordering of $G$, which is similar to the result about the maximum cardinality search (MCS for short) algorithm on chordal graphs J.R.S. Blair, B.W. Peyton, An introduction to chordal graphs and clique trees, IMA Volumes in Mathematics and its Applications, 56 (1993) pp. 1–30] and the result about the lexicographical breadth-first search (LexBFS for short) algorithm on general graphs A. Berry, J.-P. Bordat, Separability generalizes Dirac’s theorem, Discrete Appl. Math., 84 (1998) 43–53]. As a corollary, we can obtain a simple algorithm on a chordal graph to generate all minimal separators and all maximal cliques.