# Properties and Recognition of Atom Graphs
## 6 Atom Graph and Union Join Graph
Whereas the number of graphs having \(2n-1\) given vertices is \(2^{(2n-1)(2n-2)/2}\), i.e., \((2^{2n-1})^{n-1}\). Note that this algorithm is still quite intractable except for very small graphs. Theorem 1: _An atom graph can be recognized in \(O(m^{n-1}n^{5})\) time._  
Proof. : We assume without loss of generality that \(G\) is connected. The idea is to consider each spanning tree of \(G\) and each ordering of its edges. For that, we associate each edge of \(G\) with an integer from 1 to \(m\). A subset of \(n-1\) edges (potential set of edges of a spanning tree) is represented by the sequence of their associated integers in increasing order. There are \({m\choose n-1}\) such sequences that we process in lexicographic order. As finding the next sequence in lexicographic order and checking that it defines a spanning tree (connected and covering all vertices) take \(O(n)\) time, this process is in \(O(n{m\choose n-1})\) time, and therefore in \(O(nm^{n-1}/(n-1)! )\) time. An ordering of the edges is represented by the sequence of their associated integers. There are \((n-1)!\) such sequences that we process in lexicographic order. As finding the next sequence in this order takes \(O(n)\) time, this process is in \(O(n(n-1)! )\) time. Now, given a spanning tree \(T\) and an ordering \((e_{1},\ldots,e_{p})\), for each \(i\) from 1 to \(p\), \(V_{i}\) is necessarily the set defined as follows. Let \(e_{i}=x_{i}y_{i}\), and \(V_{x_{i}}\) (resp. \(V_{y_{i}}\)) be the connected component of \(T-\{e_{j},\ j\in[1,i]\}\) containing \(x_{i}\) (resp. \(y_{i}\)). \(V_{i}\) is the union of the set of neighbors of \(x_{i}\) in \(V_{y_{i}}\) and the set of neighbors of \(y_{i}\) in \(V_{x_{i}}\). Computing \(V_{i}\) and checking its convexity takes \(O(n)\) time, and therefore \(O(n^{2})\) time for all \(i\). If \(e_{j}\) is an edge of \(T(V_{i})\) then necessarily \(j\geq i\), and checking that \(V_{j}\subseteq V_{i}\) takes \(O(n)\) time, and therefore \(O(n^{3})\) time for all \(i,j\). It is sufficient to check the equivalence \"\(xy\) is an edge of \(G\) if and only if \(\{x,y\}\subseteq V_{i}\)\" for each pair \(\{x,y\}\) such that \(x\) is in \(V_{x_{i}}\) and \(y\) is in \(V_{y_{i}}\) (\(V_{x_{i}}\) and \(V_{y_{i}}\) defined as above), since these pairs are exactly the pairs \(\{x,y\}\) such that \(i=min\{j\in[1,p]\), \(e_{j}\)_is an edge of_\(P_{T}(x,y)\}\). This process adds a time complexity in \(O(n^{2})\) for all \(i\), since the sets \(V_{x_{i}}\) and \(V_{y_{i}}\) have already been computed and each pair \(\{x,y\}\) is checked exactly once. Hence, the algorithm is in \(O(nm^{n-1}/(n-1)!*n(n-1)! )*n^{3})\) time, i.e., in \(O(m^{n-1}n^{5})\) time. We use Characterization 13 to show that the \(k\)-sun is not an atom graph if \(k\geq 4\). We recall that the 3-sun is an atom graph (it is the atom graph of the graph shown in Figure 5). **Property 14**. : _There is no integer \(k\geq 4\) such that the \(k\)-sun is an atom graph._  
Proof. : We assume for contradiction that there is an integer \(k\geq 4\) such that the \(k\)-sun is an atom graph, and therefore an AG-expanded tree. Let \(G=(V,E)\) be a \(k\)-sun and let \((T,(e_{1},\ldots,e_{p}),(V_{1},\ldots,V_{p}))\) be an AG-structure of \(G\). Let \(C\) be the clique of \(G\) of size \(k\), let \(D=V\setminus C\), let \(D_{1}\) (resp. \(D_{2}\)) be the set of vertices of \(D\) of degree \(1\) (resp. \(2\)) in \(T\), and let \(C_{2}=C\cup D_{2}\). \(T(C_{2})\) is a subtree of \(T\). Let \(i_{0}=min\{i\in[1,p]\), \(e_{i}\)_is an edge of_\(T(C_{2})\}\), let \(e_{i_{0}}=x_{1}x_{2}\), and for each \(i\in\{1,2\}\) let \(X_{i}\) be the connected component of \(T\)-\(\{e_{i_{0}}\}\) containing \(x_{i}\) and let \(y_{i}\) be equal to \(x_{i}\) if \(x_{i}\in C\) and to the neighbor of \(x_{i}\) in \(X_{i}\) otherwise, so that in both cases \(y_{i}\in C\cap X_{i}\). Let us show that \(C_{2}\subseteq V_{i_{0}}\). Let us first show that \(C\subseteq V_{i_{0}}\). Let \(x\in C\), and let \(i,j\) such that \(x\in X_{i}\) and \(\{i,j\}=\{1,2\}\).