# Properties and Recognition of Atom Graphs
## 6 Atom Graph and Union Join Graph  
We immediately deduce from Properties 4 and 6 and from Characterization 7 the following result, which will be useful to prove the characterization of an atom graph as an AG-expanded tree in Section 7. **Characterization 10**. : _A connected graph. \(G\) is an atom graph if and only if there is a join tree \(T\) of a connected \(\alpha\)-acyclic hypergraph such that \(G\) is isomorphic to \(tuj(T)\)._  
Let \(H\) be a connected \(\alpha\)-acyclic hypergraph. By Property 6 there is a connected chordal graph \(G\) such that \(UJ(H)=AG(G)\) and \(L(H)=CG(G)\) up to some isomorphism. It follows that \(UJ(H)\) is a subgraph of \(L(H)\) with the same node set and that we can deduce from Characterization 9 the following characterizations of a connected \(\alpha\)-acyclic hypergraph having the same union join graph and line graph. **Characterization 11**. : _Let \(H\) be a connected \(\alpha\)-acyclic hypergraph. The following propositions are equivalent:_  
1. \(UJ(H)=L(H)\)_,_
2. _each cycle of_ \(L(H)\) _has two edges that are of minimum weight among the edges of this cycle and are associated with the same set,_
3. _each cycle of_ \(L(H)\) _has two edges that are of minimum weight among the edges of this cycle._  
**7. Characterizations in Terms of Spanning Trees**  
The polynomial complexity of recognizing a clique graph of a chordal graph is proved using a characterization of this graph as an _expanded tree_[17]. We recall this characterization, which will give inspiration for a characterization of an atom graph. **Definition 7**. : _A graph \(G\) is an expanded tree if there is a spanning tree \(T\) of \(G\) such that for each edge \(xy\) of \(G\), the set of vertices of \(P_{T}(x,y)\) is a clique of \(G\)._  
The clique graph of a chordal graph \(G\) is an expanded tree since any clique tree of \(G\) satisfies the condition. The converse holds by the following characterization. **Characterization 12** ([17]). : _A connected graph is a clique graph of a chordal graph if and only if it is an expanded tree._  
For instance, trees and complete graphs are clearly expanded trees, and therefore clique graphs of chordal graphs, which also follows from Characterization 14. We now come to a characterization of an atom graph in terms of a spanning tree. **Definition 8**. : _An AG-structure of a graph \(G=(V,E)\) is a triple \((T,S_{e},S_{V})\) where \(T\) is a spanning tree of \(G\), \(S_{e}\) is an ordering \((e_{1},\ldots,e_{p})\) of the edges of \(T\) and \(S_{V}\) is a sequence \((V_{1},\ldots,V_{p})\) of subsets of \(V\) such that for each \(i,j\in[1,p]\), \(T(V_{i})\) is a subtree of \(T\) containing the edge \(e_{i}\) and if \(e_{j}\) is an edge of \(T(V_{i})\) then \(j\geq i\) and \(V_{j}\subseteq V_{i}\), and for each pair \(\{x,y\}\) of \(V\), \(xy\) is an edge of \(G\) if and only if \(\{x,y\}\subseteq V_{i}\), where \(i=min\{j\in[1,p]\), \(e_{j}\) is an edge of \(P_{T}(x,y)\}\)._  
\(G\) _is an AG-expanded tree if it has an AG-structure._  
**Example 2**. : _Figure 6 shows a graph \(G\) and an AG-structure \((T,S_{e},S_{V})\) of \(G\): the edges of \(T\) are represented by full lines, \(S_{e}=(e_{1}=\{2,5\},e_{2}=\{4,5\},e_{3}=\{1,5\},e_{4}=\{3,5\})\) and \(S_{V}=(V_{1}=\{1,2,3,5\},V_{2}=\{1,3,4,5\},V_{3}=e_{3},V_{4}=e_{4})\). Underlining \(e_{i}\) means that \(V_{i}=e_{i}\). It follows that \(G\) is an AG-expanded tree, and it is an atom graph since it is isomorphic to the atom graph of the graph shown in Figure 4._As for expanded trees, each tree \(T\) is an AG-expanded tree (with the AG-structure \((T,S,S)\) where \(S\) is an arbitrary ordering of the edges of \(T\)) and each complete graph \(G\) is an AG-expanded tree (with the AG-structure \((P,S_{e},S_{V})\) where \(P\) is a spanning path of \(G\), \(S_{e}\) is a natural ordering \((e_{1},\ldots,e_{p})\) of the edges of \(P\) and \(S_{V}\) is the sequence \((V_{1},\ldots,V_{p})\) such that for each \(i\) from \(1\) to \(p\)\(V_{i}\) is the union of the edges \(e_{j}\), \(j\geq i\).