# Properties and Recognition of Atom Graphs
## 2 Preliminaries
: _Let \(G=(V,E)\) be a connected chordal graph, let \(T\) be a clique tree of \(G\), and let \(S\) be a minimal separator of \(G\). The number of edges \(XY\) of Tsuch that \(S=X\cap Y\) is equal to the number of full components of \(S\) in \(G\) minus \(1\)._  
If \(G\) is a disconnected chordal graph, we associate with \(G\) a forest whose connected components are clique trees of the connected components of \(G\). A clique tree (forest) can be computed in linear time [15]. A _block graph_ is a (necessarily chordal) graph whose minimal separators are of size \(1\). _Atom_. In this paper, we do not use the definition of atoms as the vertex sets produced by clique minimal separator decomposition, but their following characterization. **Characterization 2** ([2]). : _Let \(G=(V,E)\) be a graph and let \(A\) be a subset of \(V\). \(A\) is an atom of \(G\) if and only if \(A\) is an inclusion-maximal subset of \(V\) inducing a connected subgraph of \(G\) with no clique separator._  
We denote the set of atoms of \(G\) by \(\mathcal{A}(G)\). A graph has at most \(n\) atoms. _Atom tree._  
**Definition 2** ([20]). : _Let \(G=(V,E)\) be a connected graph. An atom tree of \(G\) is a tree \(T=(\mathcal{A}(G),E_{T})\) such that for each vertex \(x\) of \(G\), the set \(\mathcal{A}_{x}\) of nodes of \(T\) containing \(x\) induces a subtree of \(T\)._  
**Characterization 3** ([20]). : _Let \(G=(V,E)\) be a connected graph, let \(T\) be an atom tree of \(G\), and let \(S\subseteq V\); then \(S\) is a clique minimal separator of \(G\) if and only if there is an edge \(AB\) of \(T\) such that \(S=A\cap B\)._  
_Atom graph._  
**Definition 3** ([21]). : _The atom graph of a graph \(G\), denoted by \(AG(G)\), is the graph \((\mathcal{A}(G),E^{\prime})\), where \(\mathcal{A}(G)\) is the set of atoms and \(E^{\prime}\) the set of pairs \(\{A,B\}\) of \(\mathcal{A}(G)\) such that \(A\cap B\) is a clique minimal \((A\setminus B)(B\setminus A)\)-separator of \(G\)._  
**Property 2** ([21]). : _Let \(A\) and \(B\) be distinct atoms of a graph \(G\). Then, \(G(A\setminus B)\) is connected and \(A\cap B\subseteq N_{G}(A\setminus B)\)._  
**Property 3** ([2,21]). : _Let \(G=(V,E)\) be a connected graph, and let \(G^{+}\) be the graph obtained from \(G\) by adding all the edges that are necessary to make each atom of \(G\) into a clique. Then \(G^{+}\) is chordal, its clique trees are the atom trees of \(G\), its atom graph is the atom graph of \(G\) and for each clique \(S\) of \(G\), the full components of \(S\) in \(G^{+}\) are the full components of \(S\) in \(G\)._  
**Characterization 4** ([21]). : _The atom graph of a connected graph \(G\) is the union of all the atom trees of \(G\)._  
**Characterization 5** ([21]). : _Let \(G\) be a connected graph, let \(A\) and \(B\) be distinct atoms of \(G\) and let \(T\) be an atom tree of \(G\). Then, \(AB\) is an edge of \(AG(G)\) if and only if there is an edge \(A^{\prime}B^{\prime}\) on the path \(P_{T}(A,B)\) from \(A\) to \(B\) in the tree \(T\) such that \(A\cap B=A^{\prime}\cap B^{\prime}\)._By definition of an atom tree, for each pair \(\{A,B\}\) of nodes of an atom tree \(T\) and each edge \(A^{\prime}B^{\prime}\) of \(P_{T}(A,B)\), \(A\cap B\subseteq A^{\prime}\cap B^{\prime}\). It follows that in Characterization 5, the equality \(A\cap B=A^{\prime}\cap B^{\prime}\) can be replaced by \(A^{\prime}\cap B^{\prime}\subseteq A\cap B\), \(|A^{\prime}\cap B^{\prime}|=|A\cap B|\) or \(|A^{\prime}\cap B^{\prime}|\leq|A\cap B|\). We associate with each edge \(AB\) of an atom tree or an atom graph the set \(A\cap B\) of weight \(|A\cap B|\). _Clique graph of a chordal graph._ A graph \(G\) is a _clique graph of a chordal graph_ if there is a chordal graph \(G^{\prime}\) such that \(G\) is isomorphic to the clique graph of \(G^{\prime}\). **Characterization 6** ([25]).