## 8 The MLS-Terminal Vertex Problem on Chordal Graphs  
To conclude our investigation of the extremities defined by the MLS family of algorithms, we will ask the following question:  
\"Given a graph \(G\) and a vertex \(x\) of \(G\), is there an MLS execution which gives number 1 to vertex \(x\)?\"  
We call this the MLS-Terminal Vertex Problem.  
[PERSON] [20] showed that LexBFS-Terminal Vertex Problem is NP-complete even for weakly chordal graphs and Hereditary Dominating Path graphs, and left open its complexity on chordal graphs.  
We give a simple characterization of MNS-terminal vertices in a chordal graph:  
**Characterization 8.1**: _For any chordal graph \(G\) and any vertex \(x\) of \(G\), \(x\) is MNS-terminal if and only if \(x\) is simplicial and the substars of \(x\) are totally ordered by inclusion._  
As a consequence, the MLS-Terminal Vertex Problem is polynomial for the class of chordal graphs.  
The proof of Characterization 8.1 uses the following well-known property of chordal graphs:  
**Property 8.2**: _[_21_]_ _(confluence vertex property) Let \(G=(V,E)\) be a chordal graph, let \(C\) be a non-empty connected subset such that \(N(C)\) is a clique. Then \(\exists z\in C\) such that \(N(C)\subseteq N(z)\)._  
**Proof:** (of Characterization 8.1) We will use Algorithm MNS for our proof. If \(x\) is MNS-terminal then \(x\) is simplicial since MNS computes a peo of \(G\) and by Theorem 4.1, the neighborhoods are totally ordered by inclusion.  
Conversely, we suppose that \(x\) is simplicial and neighborhoods of connected components of \(G(V-N[x])\) are totally ordered by inclusion. Let \((C_{1},C_{2},...,C_{q})\) be an ordering on the components of \(G(V-N(x))\) such that \(\forall j\in[1,q-1]\), \(N(C_{j})\subseteq N(C_{j+1})\), with \(C_{q}=\{x\}\). For any \(j\in[1,q]\), let \(S^{\prime}_{j}=N(C_{j})-N(C_{j-1})\), let \(T^{\prime}_{j}=S^{\prime}_{j}\cup C_{j}\) and let \(c_{j}\in C_{j}\) such that \(N(C_{j})\subseteq N(c_{j})\) (\(c_{j}\) exists by Property 8.2 because as \(x\) is simplicial, \(C_{j}\) is simplicial too). Let us show that there is a MNS execution on \(G\) numbering the sets \(T^{\prime}_{j}\) in increasing order. We prove by induction on \(j\) that there is a MNS execution on \(G\) numbering successively \(T^{\prime}_{1}\), \(T^{\prime}_{2}\),..., \(T^{\prime}_{j}\) first. It obviously holds for \(j=0\). Now suppose that it holds for \(j-1\) for some \(j\leq q\). After numbering \(T^{\prime}_{1}\), \(T^{\prime}_{2}\),..., \(T^{\prime}_{j-1}\), for every unnumbered vertex \(t\), \(l(t)\) is the set of numbered neighbors of \(t\), so \(l(t)\subseteq N(C_{j-1})\subseteq N(C_{j})\subseteq N(c_{j})\). So \(c_{j}\) can be chosen at that step. It remains to show that at any step after numbering \(c_{j}\) and some, but not all, vertices of \(T^{\prime}_{j}\), it is possible to choose the next vertex in \(T^{\prime}_{j}\). Let \(y\) be an unnumbered vertex in \(T^{\prime}_{j}\), \(\mu\) be a \(c_{j}y\)-path whose internal vertices are in \(C_{j}\), let \(y^{\prime}\) be the first unnumbered vertex of \(\mu\) from \(c_{j}\) and \(z^{\prime}\) be the numbered vertex preceding \(y^{\prime}\) on \(\mu\). Then \(z^{\prime}\in l(y^{\prime})\). Let \(y^{\prime\prime}\) be an unnumbered vertex whose label is maximal among those of unnumbered vertices \(t\) such that \(z^{\prime}\in l(t)\). So the label of \(y^{\prime\prime}\) is maximal among those of all unnumbered vertices and \(y^{\prime\prime}\in T^{\prime}_{j}\) (since \(z^{\prime}\in C_{j}\cap N(y^{\prime\prime})\)). Thus \(y^{\prime\prime}\) can be chosen at that step. Hence \(T^{\prime}_{1}\), \(T^{\prime}_{2}\),..., \(T^{\prime}_{q}\) can be numbered in increasing order. As the vertices of \(T^{\prime}_{q}\) form a clique module (since \(x\) is simplicial) they can be numbered in an arbitrary order and \(x\) can be numbered last.  
The MLS orderings of a graph are exactly its MNS orderings [12], so its MLS-terminal vertices are exactly its MNS-terminal vertices. \(\Box\)