Moplex orderings generated by the LexDFS algorithm

Let GG be a graph with vertex set VV. A moplex   of GG is both a clique and a module whose neighborhood is a minimal separator in GG or empty. A moplex ordering   of GG is an ordered partition (X1,X2,⋯,Xk)(X1,X2,⋯,Xk) of VV for some integer kk into moplexes which are defined in the successive transitory elimination graphs, i.e., for 1⩽i⩽k−11⩽i⩽k−1, XiXi is a moplex of the graph GiGi induced by ∪j=ikXj and XkXk 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 GG belongs to a moplex whose vertices are numbered consecutively and further that the LexDFS algorithm on GG defines a moplex ordering of GG, 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.