## 2 Notations and Previous Results
### Minimal separators and chordal graphs  
A notion which is central to chordal graphs and their extremities is that of minimal separation:  
**Definition 2.1**: _A subset \(S\) of vertices of a connected graph \(G\) is called a separator (or sometimes a cutset) if \(G(V-S)\) is not connected. A separator \(S\) is called an \(ab\)-separator if \(a\) and \(b\) lie in different connected components of \(G(V-S)\), a minimal \(ab\)-separator if \(S\) is an \(ab\)-separator and no proper subset of \(S\) is an \(ab\)-separator. A separator \(S\) is a minimal separator, if there is some pair \(\{a,b\}\) such that \(S\) is a minimal \(ab\)-separator._  
Alternately, \(S\) is a minimal separator if and only if \(G(V-S)\) has at least 2 connected components \(C_{1}\) and \(C_{2}\) such that \(N(C_{1})=N(C_{2})=S\), and \(S\) is a minimal separator for any \(\{x,y\}\) with \(x\in C_{1}\) and \(y\in C_{2}\). **Example 2.2**: _In Figure 1, the minimal separators of the graph are: \(\{b,c\},\{c,d\},\{b,f\}\). Minimal separator \(\{b,c\}\) defines connected components \(\{e,f\}\) and \(\{a,d,g,h\}\). In Figure 2, the minimal separators are: \(\{b\},\{b,d\},\{e\}\). Note how minimal separator \(\{b\}\) is included in minimal separator \(\{b\}\), which minimally separates vertices \(\{e,f,g\}\) from vertices \(\{a,c,d,h\}\), while minimal separator \(\{b,d\}\) minimally separates vertices \(\{a,c\}\) from vertex \(h\)._  
**Figure 1**. Chordal graph \(H_{1}\) with set of minimal separators \(\{\{b,c\},\{c,d\},\{b,f\}\}\). The substars of \(a\) are \(\{b,c\}\). The molelexes are \(\{g,h\}\) and \(\{e\}\). Vertex \(a\) is simplicial but does not belong to a molelex. and \(\{c,d\}\). **Figure 2**. Chordal graph \(H_{2}\) with set of minimal separators \(\{\{b\},\{b,d\},\{e\}\}\). \(\{a,c\}\) is a molelex. [PERSON] [1] introduced the concept of minimal separator in order to characterize chordal graphs as the class for which every minimal separator is a clique. This notion was concurrently (though implicitly) used by [PERSON] and [PERSON] [2], as they defined the notion of _substar_: the substars of a vertex \(x\) are the minimal separators included in the neighborhood of \(x\). [2] characterized chordal graphs as the graphs for which every substar of every vertex is a clique. We will see later on in this paper that the notion of substar will help us refine some notions of extremities. **Definition 2.3**: _Let \(G=(V,E)\) be a graph, let \(x\) be a vertex of \(V\), let \((C_{i})\) be the connected components of \(G(V-N[x])\). The substars of \(x\) are the elements of \((N_{G}(C_{i}))\)._  
**Property 2.4**: _The substars of \(x\) are the minimal separators included in \(N_{G}(x)\)._  
**Example 2.5**: _In Figure 1, the connected components of \(G(V-N[a])\) are: \(C_{1}=\{e,f\}\) and \(C_{2}=\{g,h\}\). \(N(C_{1})=\{b,c\}\), \(N(C_{2}=\{c,d\}\), thus the substars of vertex \(a\) are \(\{b,c\}\) and \(\{c,d\}\)._  
[PERSON] and [PERSON] [13] refined the notion of simplicial vertex with new kind of extremity. This is a group of pairwise adjacent vertices, which they call a _moplex_:  
**Definition 2.6**: _[_13_]_ _Let \(X\) be a set of vertices of a graph \(G\). \(X\) is a moplex of \(G\) if \(X\) is a clique and a module of \(G\) whose neighborhood is a minimal separator._  
The vertices of a moplex are in some sense equivalent, because they share the same external neighborhood (_i.e._, they form a module); thus they also share the same substars. Moreover, this common neighborhood is a minimal separator, which means that there is one largest substar (which includes all the other substars). Note that a moplex \(X\) may contain a single vertex \(x\); in this case we will call \(X\) a _trivial moplex_. In Figure 1, \(\{g,h\}\) is a moplex, \(e\) is a (trivial) moplex. In Figure 2, \(\{a,c\}\) forms a moplex, with substars \(\{b\}\) and \(\{b,d\}\).