# Properties and Recognition of Atom Graphs
## Atom Graph Subclasses  
### Atom Graphs of \(\mathcal{G}_{nine}\)  
**Notation 2**. : \(\mathcal{G}_{nine}\) _denotes the class of graphs whose clique minimal separators are pairwise non-inclusive (nine stands for non-inclusive)._  
Figure 8: The 4-sun is a join-path-expanded tree. Equivalently, \(\mathcal{G}_{ninc}\) is the class of graphs whose clique minimal separators have only full components (since the minimal separators that are subsets of a minimal separator \(S\) in a connected graph \(G\) are the neighborhoods of the connected components of \(G(V\setminus S)\)). We recall that a block graph is a chordal graph whose minimal separators are of size \(1\). Each block graph is in \(\mathcal{G}_{ninc}\). As announced in Section 4, the atom graph of a graph of \(\mathcal{G}_{ninc}\) is necessarily chordal. Moreover, it is a block graph and is an atom graph of a block graph. **Characterization 14**. : _Let \(G\) be a connected graph. The following propositions are equivalent._  
1. \(G\) _is an atom graph of a graph of_ \(\mathcal{G}_{ninc}\)_,_
2. \(G\) _is a block graph,_
3. \(G\) _is an atom graph of a block graph,_
4. \(G\) _is a clique graph of a block graph,_  
To prove Characterization 14 we will use the following results. We first recall a characterization of the edges of the atom graph that are associated with a given clique minimal separator. **Characterization 15** ([21]). : _Let \(G\) be a connected graph, let \(T\) be an atom tree of \(G\) and let \(S\) be a minimal separator of \(G\). Then the edges of \(AG(G)\) associated with \(S\) are the pairs of nodes of \(T\) whose endpoints are in different connected components of \(T(\mathcal{A}_{S})-E_{S}\), where \(\mathcal{A}_{S}\) is the set of nodes of \(T\) containing \(S\) and \(E_{S}\) is the set of edges of \(T\) associated with \(S\)._  
**Lemma 5**. : _Let \(G\) be a connected graph of \(\mathcal{G}_{ninc}\). Then \(AG(G)\) is a block graph, and if \(G\) has at least two atoms then the maximal cliques of \(AG(G)\) are the sets \(\mathcal{A}_{S}\) of atoms of \(G\) containing \(S\) for each clique minimal separator \(S\) of \(G\), and each edge in the clique \(\mathcal{A}_{S}\) is associated with \(S\)._  
Proof. : If \(G\) has a unique atom then \(AG(G)\) is clearly a block graph. We assume now that \(G\) has at least two atoms. Let \(S\) be a clique minimal separator of \(G\), let \(T\) be an atom tree of \(G\), and let \(\mathcal{A}_{S}\) and \(E_{S}\) be defined as in Characterization 15. As the edges of \(T(\mathcal{A}_{S})\) are associated with clique minimal separators containing \(S\) and \(G\in\mathcal{G}_{ninc}\), all the edges of \(T(\mathcal{A}_{S})\) are in \(E_{S}\). It follows from Characterization 15 that \(\mathcal{A}_{S}\) is a clique of \(AG(G)\) and each edge in \(\mathcal{A}_{S}\) is associated with \(S\). Hence, to show that the maximal cliques of \(AG(G)\) are the sets \(\mathcal{A}_{S}\), it is sufficient to show that each element of \(\mathcal{K}(AG(G))\) is a subset of \(\mathcal{A}_{S}\) for some clique minimal separator \(S\). Let \(\mathcal{K}\in\mathcal{K}(AG(G))\). As \(G\) has at least two atoms \(|\mathcal{K}|\geq 2\). Let \(\{X,Y\}\subseteq\mathcal{K}\) and let \(S=X\cap Y\). Let us show that \(\mathcal{K}\subseteq\mathcal{A}_{S}\). Let \(Z\in\mathcal{K}\). Let us show that \(Z\in\mathcal{A}_{S}\). It is evident if \(Z\in\{X,Y\}\). Otherwise by Property 8 and the fact that \(G\in\mathcal{G}_{ninc}\), the three edges of the triangle \((X,Y,Z)\) are associated with \(S\), and therefore \(Z\in\mathcal{A}_{S}\). Hence, \(\mathcal{K}\subseteq\mathcal{A}_{S}\). Hence, the maximal cliques of \(AG(G)\) are the sets \(\mathcal{A}_{S}\) for each clique minimal separator \(S\). Let us show that \(AG(G)\) is chordal. Let \(\mu\) be a cycle in \(AG(G)\) of length \(\geq 4\). By Property 7 two edges of \(\mu\) are associated with the same set \(S\), which are contained in the clique \(\mathcal{A}_{S}\) of \(AG(G)\). Hence, \(\mu\) has a chord, and therefore \(AG(G)\) is chordal.