# Properties and Recognition of Atom Graphs
## 6 Atom Graph and Union Join Graph
As \(xy\) is an edge of \(G\) if and only if \(\{x,y\}\subseteq V_{i}\), it is sufficient to show that \(\{x,y\}\subseteq V_{i}\) if and only if \(A_{x}A_{y}\) is an edge of \(tuj(T^{\prime})\). We assume that \(\{x,y\}\subseteq V_{i}\). Let us show that \(A_{x}A_{y}\) is an edge of \(tuj(T^{\prime})\). It is sufficient to show that \(A_{x_{i}}\cap A_{y_{i}}\subseteq A_{x}\cap A_{y_{i}}\). Let \(v\in A_{x_{i}}\cap A_{y_{i}}\), and let \(j\in[1,p]\) such that \(v=v_{j}\). As \(e_{i}\) is an edge of \(T(V_{j})\), \(V_{i}\subseteq V_{j}\), so \(\{x,y\}\subseteq V_{j}\), i.e., \(v_{j}\in A_{x}\cap A_{y}\), and therefore \(v\in A_{x}\cap A_{y}\). Hence, \(A_{x_{i}}\cap A_{y_{i}}\subseteq A_{x}\cap A_{y_{i}}\). Conversely, we assume that \(A_{x}A_{y}\) is an edge of \(tuj(T^{\prime})\). Let us show that \(\{x,y\}\subseteq V_{i}\). Let \(j\in[1,p]\) such that \(e_{j}\) is an edge of \(P_{T}(x,y)\) and \(A_{x}\cap A_{y}=A_{x_{j}}\cap A_{y_{i}}\). As \(e_{j}\) is an edge of \(T(V_{j})\), \(v_{j}\in A_{x_{j}}\cap A_{y_{j}}\), and therefore \(v_{j}\in A_{x}\cap A_{y}\), i.e., \(\{x,y\}\subseteq V_{j}\). As \(T(V_{j})\) is a subtree of \(T\), \(e_{i}\) is an edge of \(T(V_{j})\) and therefore \(i\geq j\). As \(i\leq j\) by definition of \(i\), \(i=j\) and therefore \(\{x,y\}\subseteq V_{i}\). Hence, \(G\) is isomorphic to \(tuj(T^{\prime})\). The proof of the implication from right to left of Characterization 13 describes how to define a chordal graph \(G^{\prime}\) such that \(G\) is isomorphic to \(AG(G^{\prime})\) from an AG-structure \((T,S_{e}=(e_{1},\ldots,e_{p}),S_{V}=(V_{1},\ldots,V_{p}))\) of \(G\). As the hyperedges \(A_{x}\) of the hypergraph \(H\) defined in the proof are pairwise non-inclusive (because of the presence of \(x\) in \(A_{x}\)) \(H\) is a clutter. It follows by Property 5 that \(G\) is isomorphic to the atom graph of the chordal graph \(G^{\prime}=2 SEC(H)\) having \(T^{\prime}\) as a clique tree. Note that \(G^{\prime}\) can be defined from the set \(\{V_{1},\ldots,V_{p}\}\) alone: \(G^{\prime}=(V^{\prime},E^{\prime})\), with \(V^{\prime}=V+\{v_{1},\ldots,v_{p}\}\) and \(E^{\prime}=\{xv_{i},\)\(x\in V\wedge i\in[1,p]\wedge x\in V_{i}\}+\{v_{i}v_{j},\)\(\{i,j\}\subseteq[1,p]\wedge V_{i}\cap V_{j}\
eq\emptyset\}\). **Example 3**. : _We recall in Figure 7 the graph \(G\) and its \(AG\)-structure shown in Figure 6, and we add the join tree \(T^{\prime}\) as defined in the proof of Characterization 13 and the chordal graph \(G^{\prime}\) such that \(G\) is isomorphic to \(AG(G^{\prime})\) as defined above. The edges incident to vertex \(5\) in \(G^{\prime}\) are dashed because vertex \(5\) may be removed (it is not necessary in \(A_{5}\) to turn \(H\) into a clutter). We refind the graph shown in Figure 4 whose atom graph is \(G\) (up to isomorphism)._  
Characterization 13 can be used to show that a graph is or is not an atom graph, and to deduce some properties of atom graphs. We leave as an open question whether it can be used to determine the complexity of atom graph recognition, as was the case for the characterization as an expanded tree for clique graph of a chordal graph recognition. We first define a superclass of both the classes of expanded and AG-expanded trees. **Definition 9**. : _A join-path spanning tree of a graph \(G\) is a spanning tree \(T\) of \(G\) such that for each edge \(xy\) of \(G\), there is an edge \(x^{\prime}y^{\prime}\) of \(P_{T}(x,y)\), with \(x\), \(x^{\prime}\), \(y^{\prime}\), \(y\) in this order on this path, such that each vertex of \(P_{T}(x,x^{\prime})\) is adjacent to each vertex of \(P_{T}(y^{\prime},y)\) in \(G\) (i.e., the join of the subgraphs of \(G\) induced by the paths \(P_{T}(x,x^{\prime})\) and \(P_{T}(y^{\prime},y)\) is a subgraph of \(G\)). \(G\) is an join-path-expanded tree if it has a join-path spanning tree._  
Note that if \(T\) is a join-path spanning tree of \(G\) then for each edge \(xy\) of \(G\), each vertex of \(P_{T}(x,y)\) is adjacent to \(x\) or \(y\) in \(G\)).