# Properties and Recognition of Atom Graphs
## Atom Graph Subclasses
### Atom Graphs of \(\mathcal{G}_{\mathit{ninc}}^{2}\)  
Notation 4: \(\mathcal{G}_{\mathit{ninc}}^{2}\) denotes the class of graphs whose clique minimal separators have exactly \(2\) components. \(\mathcal{G}_{\mathit{ninc}}^{2}\subseteq\mathcal{G}_{\mathit{ninc}}\) since a minimal separator has at least two full components. Thus, \(\mathcal{G}_{\mathit{ninc}}^{2}\) is the set of graphs of \(\mathcal{G}_{\mathit{ninc}}\) whose clique minimal separators have exactly two full components. The equivalence between items 1 and 3 of Characterization 16 is proved in [24] for chordal graphs. **Characterization 16**. : _Let \(G\) be a connected graph. The following propositions are equivalent._  
1. \(G\) _is a graph of_ \(\mathcal{G}_{\mathit{ninc}}^{2}\)_;_
2. \(AG(G)\) _is a tree;_
3. \(G\) _has a unique atom tree;_
4. _The sets associated with the edges of_ \(AG(G)\) _are pairwise distinct;_
5. _Each minimal separator of_ \(G\) _is a subset of exactly_ \(2\) _atoms of_ \(G\)  
Figure 9: A graph of \(\mathcal{G}_{\mathit{ninc}}\), its atom graph \(G\), which is a block graph, and the block graph \(G^{\prime}=RetroCG(G)\) whose atom graph is isomorphic to \(G\). Proof. : Let \(S\) be a clique minimal separator of \(G\), let \(\mathcal{A}_{S}\) be the set of atoms of \(G\) containing \(S\), let \(T\) be a clique tree of \(G\), and let \(E_{S}\) (resp. \(E_{S}^{\prime}\)) be the set of edges of \(T\) (resp. \(AG(G)\)) associated with \(S\). By Properties 1 and 3 the number of full components of \(S\) in \(G\) is equal to \(|E_{S}|+1\). \(1\Rightarrow 5\): as \(G\in\mathcal{G}_{ninc}\), each edge of \(T(\mathcal{A}_{S})\) is in \(E_{S}\), and as \(S\) has exactly two full components, \(|E_{S}|=1\). Hence \(T(\mathcal{A}_{S})\) has a unique edge, and therefore two nodes. \(5\Rightarrow 4\): each edge of \(E_{S}^{\prime}\) is a subset of \(\mathcal{A}_{S}\). \(4\Rightarrow 3\): As \(T\) is a subgraph of \(AG(G)\) by Characterization 4, \(E_{S}\subseteq E_{S}^{\prime}\) with \(1\leq|E_{S}|\leq|E_{S}^{\prime}|=1\). Hence, \(E_{S}=E_{S}^{\prime}\) for each \(S\), and therefore \(T=AG(G)\). \(3\Rightarrow 2\): it follows from Characterization 4. \(2\Rightarrow 1\): there is no clique minimal separator \(S^{\prime}\) stricly containing \(S\), otherwise by Characterization 15 there would be a triangle in \(AG(G)\) whose edges are associated with \(S^{\prime}\), \(S\) and \(S\), respectively, and \(|E_{S}|=1\), otherwise by Characterization 15 again there would be a triangle in \(AG(G)\) whose edges are associated with \(S\). As this holds for each \(S\), \(G\in\mathcal{G}_{ninc}\) and each clique minimal separator has exactly \(2\) full components, i.e., \(G\in\mathcal{G}_{ninc}^{2}\). **Characterization 17**. : _A connected graph is an atom graph of a graph of \(\mathcal{G}_{ninc}^{2}\) if and only if it is a tree._  
Proof. : The implication from left to right follows from Characterization 16. The converse implication follows from the fact that by Characterization 14, a tree is an atom graph, and from Characterization 16. We deduce from Theorem 2 and Characterizations 16 and 17 the following corollary. **Corollary 5**. : _Recognition of an atom graph of a graph of \(\mathcal{G}_{ninc}^{2}\) takes linear time, and if it is the case then a block graph of \(\mathcal{G}_{ninc}^{2}\) whose atom graph is isomorphic to the input graph can be computed on \(O(n^{2})\) time._  
Contrary to the block graphs which are the atom graphs of block graphs, the trees are not the atom graphs of trees. As a non-path tree has a vertex of degree at least 3, its atom graph has a clique of size at least 3 and therefore is not a tree. It follows that conversely, a non-path tree is not an atom graph of a tree since it is an atom graph of neither a path nor a non-path tree. We easily check that the paths are the atom graphs of paths (though a path may be the atom graph of a non-path graph) and that the paths are the trees of \(\mathcal{G}_{ninc}^{2}\).