# Properties and Recognition of Atom Graphs
## 6 Atom Graph and Union Join Graph
We immediately deduce from the characterizations of a clique graph of a chordal graph and an atom graph as an expanded tree and an AG-expanded tree, respectively, the following property. **Property 11**. : _Each connected atom graph (resp. clique graph of a chordal) is a join-path-expanded tree._  
As the classes of clique graphs of chordal graphs and atom graphs are inclusion-uncomparable, they are necessarily strict subclasses of the class of join-path-expanded trees, so having a join-path spanning tree is a necessary, but non-sufficient, condition for a connected graph to be an atom graph (or a clique graph of a chordal graph). **Property 12**. : _No cycle of length at least \(4\) is an atom graph._  
Proof. : We assume for contradiction that some cycle \(G\) of length at least \(4\) is an atom graph. Then by Property 11\(G\) has a join-path spanning tree \(T\), which is necessarily a path whose extremities \(x\) and \(y\) are adjacent in \(G\). As \(T\) is a join-path spanning tree of \(G\), each vertex of \(G\) is adjacent to \(x\) or \(y\) in \(G\), a contradiction. Though a \(C_{4}\) is not an atom graph, the graph obtained from a \(C_{4}\) by adding a universal vertex is an atom graph, as is shown in Figure 7. We have the following result. **Corollary 3**. : _The class of atom graphs is not hereditary._  
Note that these results also hold for clique graphs of chordal graphs. No cycle of length at least \(4\) is a clique graph of a chordal graph for the same reason as for atom graphs. As any graph having a universal vertex is a clique graph of a chordal graph (by Characterization 6, considering the spanning tree whose edges are the edges incident to a universal vertex) the class of clique graphs of chordal graphs also fails to be hereditary. We deduce from the proof of Characterization 13 the following property. **Property 13**. : _Each connected atom graph of order \(n\) is isomorphic to the atom graph of some chordal graph of order \(2n-1\) whose minimal separators have exactly \(2\) full components._  
Figure 7: Construction of a graph \(G^{\prime}\) such that \(G\) is isomorphic to \(AG(G^{\prime})\) from an AG-structure of \(G\). Proof. : In the proof of Characterization 13 we define from an AG-structure of a connected graph \(G\) of order \(n\) a clique tree \(T^{\prime}\) of a chordal graph \(G^{\prime}\) such that \(G\) is isomorphic to \(AG(G^{\prime})\). \(G^{\prime}\) has \(n+p\) vertices, where \(p\) is the number of edges of a spanning tree of \(G\), so \(G^{\prime}\) is of order \(2n-1\). Let us show that the sets associated with the edges of \(T^{\prime}\) are pairwise distinct. Let \(i,j\in[1,p]\) such that. \(A_{x_{i}}\cap A_{y_{i}}=A_{x_{j}}\cap A_{y_{j}}\). Let us show that \(i=j\). As \(e_{i}\) is an edge of \(T(V_{i})\), \(v_{i}\in A_{x_{i}}\cap A_{y_{i}}\), so \(v_{i}\in A_{x_{j}}\cap A_{y_{j}}\), i.e., \(e_{j}\) is an edge of \(T(V_{i})\), and therefore \(j\geq i\). Symmetrically \(i\geq j\), so \(i=j\). Hence, the sets associated with the edges of \(T^{\prime}\) are pairwise distinct, so by Property 1 each minimal separator of \(G^{\prime}\) has exactly 2 full components. Property 13 provides a polynomial certificate for atom graph recognition. Given a graph \(G\) of order \(n\), the certificate is composed of a graph \(G^{\prime}\) of order \(2n-1\), its atom graph \(G^{\prime\prime}\) and an isomorphism \(f\) from \(G\) to \(G^{\prime\prime}\). We can check in polynomial time that \(G^{\prime\prime}\) is the atom graph of \(G^{\prime}\) and that \(f\) is an isomorphism from \(G\) to \(G^{\prime\prime}\). Corollary 4: _Atom graph recognition is in NP._  
Property 13 also provides a brute force algorithm recognizing an atom graph: computing all the graphs having \(2n-1\) given vertices, and for each one of these graphs satisfying the conditions of Property 13, computing its atom graph and determining whether it is isomorphic to the input graph. We deduce from Characterization 13 another brute force algorithm which is (relatively!) more efficient since it runs in \(O(m^{n-1}n^{5})\) time.