Properties and Recognition of Atom Graphs

Abstract

The atom graph of a connected graph is a graph whose vertices are the atoms obtained by clique minimal separator decomposition of this graph, and whose edges are the edges of all its atom trees. A graph G is an atom graph if there is a graph whose atom graph is isomorphic to G. We study the class of atom graphs, which is also the class of atom graphs of chordal graphs, and the associated recognition problem. We prove that each atom graph is a perfect graph and give a characterization of atom graphs in terms of a spanning tree, inspired by the characterization of clique graphs of chordal graphs as expanded trees. We also characterize the chordal graphs having the same atom and clique graph, and solve the recognition problem of atom graphs of two graph classes.

1. Introduction

Decomposition by clique separators was introduced by Tarjan [1] in 1985 to help the resolution of hard problems. This decomposition of a graph G can be represented by a binary tree whose nodes are vertex subsets of G. Its root is the vertex set of G, and for each node $V^{\prime }$, if $G\left(V^{\prime }\right)$ has a clique separator then the node $V^{\prime }$ has two children $A\cup S$ and $B\cup S$, where $\{A,B,S\}$ is a partition of $V^{\prime }$ and S is a clique $AB$-separator, otherwise, $V^{\prime }$ is a leaf of the tree and is called an atom. However, the set of atoms depends on the choice of the clique separators. Leimer [2] proved that the set of atoms is uniquely defined if the set S is a clique minimal $AB$-separator in the definition above, leading to the notion of clique minimal separator decomposition.

Clique minimal separator decomposition has been studied in different contexts. A general survey is given in [3], and the complexity of its computation is improved in [4]. This decomposition is investigated in some particular graph classes [5,6,7,8,9,10] and is used in the domains of databases [11], text mining [12], and biology [13,14].

The atoms of a chordal graph are its maximal cliques. Several graphs are defined from a connected chordal graph G, whose nodes are the maximal cliques of G: its clique trees [15,16], its clique graph [17], which is the intersection graph of its maximal cliques, and the union of its clique trees, which is a subgraph of its clique graph and is shown to better capture the structure of G than its clique graph [18,19].

These graphs, defined from a connected chordal graph, can be generalized to any connected graph G, whose nodes are the atoms of G: its atom trees [20] and its atom graph, which is the union of its atom trees and a subgraph of the intersection graph of its atoms, which better captures the structure of G than the intersection graph of its atoms. Hence, the atom trees of a connected chordal graph are its clique trees, and its atom graph is a subgraph of its clique graph.

The notion of atom graph was introduced in 2007 in [14] to visualize biological clusters. Several algorithms computing the atom graph of a graph are presented in [21] and extended to the computation of the union join tree of an $\alpha$-acyclic hypergraph.

In this paper, we focus on the class of atom graphs. A graph G is an atom graph if there is a graph whose atom graph is isomorphic to G. First of all, we deduce from known results that the atom graphs are exactly the atom graphs of chordal graphs, which is not the case for clique graphs. We prove that each atom graph is a perfect graph, i.e., a graph such that each induced subgraph has the same chromatic and clique number, or equivalently (Strong Perfect Graph Theorem), a graph having no induced odd hole nor induced odd anti-hole. We give a characterization of an atom graph in terms of a spanning tree, leading to an algorithm recognizing an atom graph in $O\left(m^{n-1}{n}^5\right)$ time. We also define two graph classes such that the atom graphs of the graphs of these classes can be recognized in linear time.

The paper is organized as follows. Section 2 provides some preliminaries. Section 3 characterizes an atom graph as an atom graph of a chordal graph. Section 4 proves that each atom graph is perfect. Section 5 characterizes the chordal graphs having the same atom and clique graph. Section 6 and Section 7 provide characterizations of an atom graph in terms of a hypergraph and a spanning tree, respectively. Section 8 investigates the atom graphs of the graphs of two graph classes. We conclude in Section 9.

2. Preliminaries

The preliminaries of this paper are similar to those of [21]. In order to avoid useless repetition, we only recall here the main definitions, results and notations, and add some results from [21], the new notions appearing in this paper and the results that are explicitly referred to in this paper. We invite the reader to have a look at the preliminaries section of [21] for more detail and an example.

We consider here finite and undirected graphs. For a graph $G=(V,E)$, $n=\left|V\right|$ (order of G) and $m=\left|E\right|$. For any subset X of V, $G\left(X\right)$ denotes the subgraph of G induced by S. For any vertex v of G, $N_G\left(v\right)$ denotes the neighborhood of v in G, i.e., $N_G\left(v\right)=\{w\in V|vw\in E\}$, and $N_G\left[v\right]$ denotes its closed neighborhood in G, i.e., $N_G\left[v\right]=\left\{v\right\}\cup N_G\left(v\right)$. For any subset X of V, $N_G\left(X\right)=\left({\cup }_{v\in X}{N}_G\left(v\right)\right)\backslash X$ and $N_G\left[X\right]=X\cup N_G\left(X\right)$.

For each graph G, $\mathcal{K}\left(G\right)$ denotes the set of maximal cliques of G and the clique graph of G, denoted by $CG\left(G\right)$, is the intersection graph of $\mathcal{K}\left(G\right)$. If X and Y are nodes of a tree T, $P_T(X,Y)$ denotes the path in T between X and Y.

For each integer $k\ge 3$, a $C_k$ is a graph which is a cycle of length k and a k-sun is a graph obtained from a $C_k$ by adding for each edge $xy$ of this $C_k$ a vertex adjacent to x and y and adding all edges that are necessary to make this $C_k$ into a clique. A hole is a $C_k$ with $k\ge 5$, and an anti-hole is its complement graph. A hole or anti-hole is odd if its number of vertices is odd. G is (odd-)(anti-)hole-free if no induced subgraph of G is an (odd)(anti-)hole. We do not use the definition of a perfect graph in this paper, but we use its well-known characterization as an odd-hole-free and odd-anti-hole-free graph (Strong Perfect Graph Theorem).

Separation. Let $G=(V,E)$ be a connected graph and let S be a subset of V. S is a separator of G if $G(V\backslash S)$ is disconnected. The connected components of $G(V\backslash S)$ are called the components of S in G. For any pair $\{a,b\}$ of $V\backslash S$, S is an $ab$-separator of G if a and b are in different components of S in G. S is a minimal $ab$-separator if it is an inclusion-minimal $ab$-separator, and a minimal separator if there is some pair $\{a,b\}$ of V such that S is a minimal $ab$-separator. A full component of S in G is a component C of S in G such that $N_G\left(C\right)=S$. S is a minimal separator if S has at least two full components, and S is a minimal ab-separator if a and b lie in two different full components of S. Let A and B be two subsets of V. S is a (minimal) $AB$-separator of G if it is a (minimal) $ab$-separator of G for each $a\in A$ and each $b\in B$.

If G is disconnected, then a (minimal) ($ab$-)separator of G is a (minimal) ($ab$-)separator of one of its connected components.

Chordal graph. A graph is chordal, or triangulated, if it has no chordless cycle of length at least 4. A graph is chordal if and only if all its minimal separators are cliques [22]. A connected graph is chordal if and only if it has a clique tree [16,23].

Definition 1.

Let $G=(V,E)$ be a connected chordal graph. Aclique tree of G is a tree $T=(\mathcal{K}\left(G\right),E_T)$ such that for each vertex x of G, the set ${\mathcal{K}}_x$ of nodes of T containing x induces a subtree of T.

Characterization 1

([15]). Let $G=(V,E)$ be a connected chordal graph, let T be a clique tree of G, and let $S\subseteq V$; then S is a minimal separator of G if and only if there is an edge $XY$ of T such that $S=X\cap Y$.

Property 1

([24]). 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}\left(G\right)$. A graph has at most n atoms.

Atom tree.

Definition 2

([20]). Let $G=(V,E)$ be a connected graph. An atom treeof G is a tree $T=(\mathcal{A}\left(G\right),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]). Theatom graphof a graph G, denoted by $AG\left(G\right)$, is the graph $(\mathcal{A}\left(G\right),E^{\prime })$, where $\mathcal{A}\left(G\right)$ is the set of atoms and $E^{\prime }$ the set of pairs $\{A,B\}$ of $\mathcal{A}\left(G\right)$ such that $A\cap B$ is a clique minimal $(A\backslash B)(B\backslash A)$-separator of G.

Property 2

([21]). Let A and B be distinct atoms of a graph G. Then, $G(A\backslash B)$ is connected and $A\cap B\subseteq N_G(A\backslash 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\left(G\right)$ 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 }|\le |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]). A graph G is a clique graph of a chordal graph if and only if it has a spanning tree T such that each maximal clique of G induces a subtree of T.

$\mathbf{\alpha }$-acyclic hypergraphs. A simple hypergraph, or hypergraph for short, is a structure $H=(V,\mathcal{E})$, where V is its vertex set and $\mathcal{E}$ is a set of non-empty subsets of V, called the hyperedges of H, whose union is equal to V. A hypergraph is a clutter if the elements of $\mathcal{E}$ are pairwise non-inclusive. Its line graph, denoted by $L\left(H\right)$, is the intersection graph of $\mathcal{E}$. Its 2-section graph, denoted by $2SEC\left(H\right)$, is the graph whose vertex set is V and whose edges are the pairs of V that are contained in a hyperedge of H. H is connected if $L\left(H\right)$ is connected, or equivalently if $2SEC\left(H\right)$ is connected.

A join tree of H is a tree T whose node set is $\mathcal{E}$ and such that for each vertex x of H, the set ${\mathcal{E}}_x$ of nodes of T containing x induces a subtree of T, or equivalently, such that for each pair $\{X,Y\}$ of $\mathcal{E}$, $X\cap Y$ is a subset of each node of $P_T(X,Y)$. H is α-acyclic if it has a join tree.

Definition 4

([21]). Theunion join graphof an α-acyclic hypergraph H, denoted by $UJ\left(H\right)$, is the union of its join trees.

Definition 5

([21]). Let $G=(V,E)$ be a graph. The atom hypergraph of G is the hypergraph $H=(V,\mathcal{A}(G\left)\right)$.

Property 4

([21]). Let G be a connected graph and let H be its atom hypergraph. Then, H is a connected α-acyclic hypergraph and the atom graph of G is the union join graph of H.

Property 5.

Let H be an α-acyclic hypergraph, and let G be the 2-section graph $2SEC\left(H\right)$. Then, G is chordal and if H is a clutter then it is the atom hypergraph of G.

A non-clutter $\alpha$-acyclic hypergraph can be turned into a clutter by adding a specific element to each non-inclusion-maximal hyperedge, so any connected $\alpha$-acyclic hypergraph is an atom hypergraph up to some isomorphism as stated in Property 6.

Property 6

([21]). Let H be a connected α-acyclic hypergraph. Then, there is a connected chordal graph G such that the atom graph of G is isomorphic to the union join graph of H.

Characterization 5 can be rewritten in terms of $\alpha$-acyclic hypergraph as follows ($tuj$ stands for to union join).

Definition 6

([21]). For each join tree $T=(\mathcal{E},E_T)$ of a hypergraph, $tuj\left(T\right)$ is the graph whose node set is $\mathcal{E}$ and whose edges are the pairs $\{X,Y\}$ of $\mathcal{E}$ such that there is an edge $X^{\prime }{Y}^{\prime }$ of $P_T(X,Y)$ such that $X\cap Y=X^{\prime }\cap Y^{\prime }$ (or equivalently $X^{\prime }\cap Y^{\prime }\subseteq X\cap Y$).

Characterization 7

([21]). For each α-acyclic hypergraph H and each join tree T of H, $UJ\left(H\right)=tuj\left(T\right)$.

We associate with each edge $AB$ of a join tree or an union join graph the set $A\cap B$ of weight $|A\cap B|$.

3. Atom Graphs Are Atom Graphs of Chordal Graphs

A graph is an atom graph if it is isomorphic to the atom graph of some graph. Similarly, for a given graph class $\mathcal{C}$, a graph is an atom graph of a graph of $\mathcal{C}$ if it is isomorphic to the atom graph of some graph of $\mathcal{C}$. The atom graph recognition problem consists of determining whether a given graph is an atom graph. According to Definition 3, the connected components of the atom graph of a graph are the atom graphs of the connected components of this graph. It follows that a graph is an atom graph if and only if each one of its connected components is, so we may, without loss of generality, assume that the given graph is connected. We obtain similar definitions by replacing ’atom graph’ with ’clique graph’ for which we may also assume that the given graph is connected.

We immediately deduce from Property 3 the following characterization.

Characterization 8.

A graph is an atom graph if and only if it is an atom graph of a chordal graph.

Thus, the atom graph recognition problem can be reduced to an atom graph of a chordal graph recognition problem. It is not the case for clique graph recognition, which is NP-complete [26], whereas clique graph of a chordal graph recognition is polynomial [17]. As far as we know, the complexity of recognizing an atom graph (or equivalently an atom graph of a chordal graph) is an open question.

4. Atom Graphs Are Perfect

The clique graph of a chordal graph is not necessarily chordal, and not even perfect. For instance, the clique graph of the 5-sun is non-perfect, but its atom graph is chordal (see Figure 1), which follows from Characterization 14 below since the minimal separators of the 5-sun are pairwise non-inclusive. Introducing inclusion-comparable minimal separators, we can build a graph whose atom graph is non-chordal, as shown in Figure 2. This non-chordal atom graph is perfect though.

We will show that each atom graph is perfect, and more accurately, that it is odd-hole-free and anti-hole-free.

Notation 1.

Let $G=(V,E)$ be a graph. For each atom A and each clique S of G distinct from A, $C_S\left(A\right)$ denotes the connected component of $G(V\backslash S)$ containing $A\backslash S$.

This definition is correct since by definition of an atom, for each atom A and each clique S of G distinct from A $G(A\backslash S)$ is necessarily non-empty and connected. In particular $C_S\left(A\right)$ is defined if S is in the form $X\cap Y$ where X and Y are distinct atoms of G. Note that in that case, by Property 2, $XY$ is an edge of $AG\left(G\right)$ if and only if $C_S\left(X\right)\ne C_S\left(Y\right)$.

Lemma 1.

Let A be an atom and S a clique of a graph G such that $S\subset A$. Then $S=N_G\left(C_S\left(A\right)\right)$.

Proof. 

$N_G\left(C_S\left(A\right)\right)$ is clearly a subset of S, and it cannot be a strict subset of S since in that case it would be a clique $ab$-separator of $G\left(A\right)$ for any a in $A\backslash S$ and any b in $S\backslash N_G\left(C_S\left(A\right)\right)$. □

Lemma 2.

Let G be a graph, let μ be a cycle of $AG\left(G\right)$, let $AB$ be an edge of μ and let $S=A\cap B$; then there is an edge $A^{\prime }{B}^{\prime }$ of μ such that $C_S\left(B\right)=C_S\left(B^{\prime }\right)$ and $A^{\prime }\cap B^{\prime }\subseteq S$, with A, B, $B^{\prime }$, $A^{\prime }$ in this order on μ (with possibly $B=B^{\prime }$ or $A^{\prime }=A$).

Proof. 

As $AB$ is an edge of $AG\left(G\right)$, $C_S\left(A\right)\ne C_S\left(B\right)$. Let $A^{\prime }$ be the first node X of the path $\mu -\left\{AB\right\}$ from B such that $C_S\left(X\right)\ne C_S\left(B\right)$, and let $B^{\prime }$ be the node preceding $A^{\prime }$ on this path from B. $C_S\left(B\right)=C_S\left(B^{\prime }\right)$ with A, B, $B^{\prime }$, $A^{\prime }$ in this order on $\mu$, and as $C_S\left(A^{\prime }\right)\ne C_S\left(B\right)$, it follows that $C_S\left(A^{\prime }\right)\ne C_S\left(B^{\prime }\right)$, and therefore $A^{\prime }\cap B^{\prime }\subseteq S$. □

We deduce from Lemma 2 the following properties of atom graphs. Property 8 is proved in [18] for chordal graphs.

Property 7.

Let G be a graph, let μ be a cycle of $AG\left(G\right)$ and let S be an inclusion-minimal set among the sets associated with the edges of μ; then S is associated with at least two edges of μ.

Property 8.

Let G be a graph and let μ be a $C_3$ of $AG\left(G\right)$; then two of the clique minimal separators associated with the edges of μ are equal and included in the third one.

Lemma 3.

Let G be a connected graph, let X, $X^{\prime }$ and Y be atoms and let S be the intersection of two distinct atoms of G.

• (a). If $S\subseteq X$ and $C_S\left(X\right)\ne C_S\left(Y\right)$ then ($XY$ is an edge of $AG\left(G\right)$⇔$N\left(C_S\left(Y\right)\right)\subseteq Y$),

• (b). If $S\subseteq X\cap Y$ and $C_S\left(X\right)\ne C_S\left(Y\right)$ then $XY$ is an edge of $AG\left(G\right)$,

• (c). If $S\subseteq X\cap X^{\prime }$, $C_S\left(X\right)=C_S\left(X^{\prime }\right)$ and Y is adjacent to X but not to $X^{\prime }$ in $AG\left(G\right)$ then $C_S\left(X\right)=C_S\left(Y\right)$.

Proof. 

(a) Let $G=(V,E)$. We assume that $S\subseteq X$ and $C_S\left(X\right)\ne C_S\left(Y\right)$. Let us show that $XY$ is an edge of $AG\left(G\right)$⇔$N\left(C_S\left(Y\right)\right)\subseteq Y$.

$XY$ is an edge of $AG\left(G\right)$ if $C_{X\cap Y}\left(X\right)\ne C_{X\cap Y}\left(Y\right)$, which is still equivalent to $C_{X\cap Y}\left(Y\right)\cap (X\backslash Y)=\varnothing$. Let $C=C_{X\cap Y}\left(Y\right)$. It is sufficient to show that $N\left(C_S\left(Y\right)\right)\subseteq Y\iff C\cap (X\backslash Y)=\varnothing$.

First, note that as $N\left(C_S\left(Y\right)\right)\subseteq S\subseteq X$, we have $N\left(C_S\left(Y\right)\right)\subseteq X$, and that as $C_S\left(X\right)\ne C_S\left(Y\right)$, we have $X\cap Y\subseteq S$, and therefore $C_S\left(Y\right)\subseteq C\subseteq V\backslash (X\cap Y)$.

⇒: We assume that $N\left(C_S\left(Y\right)\right)\subseteq Y$. Then, $N\left(C_S\left(Y\right)\right)\subseteq X\cap Y$, with $C_S\left(Y\right)$ being a connected subset of $V\backslash (X\cap Y)$, so $C=C_S\left(Y\right)$ and therefore $C\cap (X\backslash Y)\subseteq C_S\left(Y\right)\cap X=\varnothing$.

⇐: We now assume that $N\left(C_S\left(Y\right)\right)⊈Y$. Let $x\in N\left(C_S\left(Y\right)\right)\backslash Y$. $x\in X\backslash Y$, and as $x\notin X\cap Y$ and x has a neighbor in $C_S\left(Y\right)$ with $C_S\left(Y\right)\subseteq C$, $x\in C$. Hence, $x\in C\cap (X\backslash Y)$, and therefore $C\cap (X\backslash Y)\ne \varnothing$.

(b) As $N\left(C_S\left(Y\right)\right)\subseteq S\subseteq Y$, by (a) $XY$ is an edge of $AG\left(G\right)$.

(c) We assume for contradiction that $S\subseteq X\cap X^{\prime }$, $C_S\left(X\right)=C_S\left(X^{\prime }\right)$, Y is adjacent to X but not to $X^{\prime }$ in $AG\left(G\right)$ and $C_S\left(X\right)\ne C_S\left(Y\right)$. By (a) on X and Y, $N\left(C_S\left(Y\right)\right)\subseteq Y$, and by (a) on $X^{\prime }$ and Y, $N\left(C_S\left(Y\right)\right)⊈Y$, a contradiction. □

Property 9.

Let G be a graph and let μ be a chordless cycle of $AG\left(G\right)$ of length at least 4; then either μ is of length 4 and its four edges are associated with the same clique minimal separator or there is an integer $k\ge 2$ such that μ is of length $2k$, there are exactly k distinct clique minimal separators associated with the edges of μ which are pairwise non-inclusive and each such separator is associated with two consecutive edges of μ.

In both cases, for each set of consecutive edges $XY$ and $YZ$ of μ associated with the same clique minimal separator S, $C_S\left(X\right)=C_S\left(Z\right)$.

Proof. 

Let $AB$ be an edge of $\mu$ such that $A\cap B$ is inclusion-minimal among the clique minimal separators associated with the edges of $\mu$ and let $S=A\cap B$. Let us first prove the following property $P_1$.

$P_1$: for each pair $\{X,Y\}$ of nodes of $\mu$ such that $C_S\left(X\right)\ne C_S\left(Y\right)$, the following propositions are equivalent:

(1) $XY$ is an edge of $\mu$,

(2) $X\cap Y=S$,

(3) $S\subseteq X\cap Y$.

$1\Rightarrow 2$: as $C_S\left(X\right)\ne C_S\left(Y\right)$$X\cap Y\subseteq S$, and by the minimality of S$X\cap Y\not\subset S$, so $X\cap Y=S$.

$2\Rightarrow 3$ is evident.

$3\Rightarrow 1$: by Lemma 3 (b) $XY$ is an edge of $AG\left(G\right)$, and therefore of $\mu$ since $\mu$ is chordless.

By Lemma 2, there is an edge $A^{\prime }{B}^{\prime }$ of $\mu$ such that $C_S\left(B\right)=C_S\left(B^{\prime }\right)$ and $A^{\prime }\cap B^{\prime }\subseteq S$, with A, B, $B^{\prime }$, $A^{\prime }$ in this order on $\mu$. By the minimality of S, $A^{\prime }\cap B^{\prime }=S$. As $AB$ is an edge of $AG\left(G\right)$, $C_S\left(A\right)\ne C_S\left(B\right)$, and therefore $C_S\left(A\right)\ne C_S\left(B^{\prime }\right)$. As $S\subseteq A\cap B^{\prime }$, by $P_1$$A{B}^{\prime }$ is an edge of $\mu$. It follows that $B=B^{\prime }$ or $A=A^{\prime }$. We assume, without loss of generality, that $B=B^{\prime }$. By $P_1$ again, as $S\subseteq A\cap A^{\prime }$ and $A{A}^{\prime }$ is not an edge of $\mu$, $C_S\left(A\right)=C_S\left(A^{\prime }\right)$. Let D be the neighbor of A on $\mu$ different from B.

First case: $C_S\left(D\right)=C_S\left(B\right)$

As $C_S\left(A\right)\ne C_S\left(D\right)$ and $AD$ is an edge of $\mu$, by $P_1$$A\cap D=S$. Hence, as $C_S\left(D\right)\ne C_S\left(A^{\prime }\right)$ and $S\subseteq D\cap A^{\prime }$, by $P_1$$D{A}^{\prime }$ is an edge of $\mu$ and $D\cap A^{\prime }=S$. Thus, $\mu$ satisfies the first alternative of Property 9 and for each set of consecutive edges $XY$ and $YZ$ of $\mu$ associated with the same clique minimal separator S, $C_S\left(X\right)=C_S\left(Z\right)$.

Second case: $C_S\left(D\right)\ne C_S\left(B\right)$

Let us show that for each node X of $\mu -\{A,B,A^{\prime }\}$, $S⊈X$. Let X be a node of $\mu -\{A,B,A^{\prime }\}$, and let Y be a node of $\{A,B\}$ such that $C_S\left(X\right)\ne C_S\left(Y\right)$ and $XY$ is not an edge of $\mu$ (if $X=D$ then $Y=B$ otherwise Y exists since neither $XA$ nor $XB$ is an edge of $\mu$ and $C_S\left(A\right)\ne C_S\left(B\right)$). By $P_1$$S⊈X\cap Y$, so as $S\subseteq Y$, $S⊈X$. It follows that for each edge $XY$ of $\mu -\left\{B\right\}$, $S⊈X\cap Y$. Hence, S is associated with no other edge than the two consecutive edges $AB$ and $A^{\prime }B$ of $\mu$. It also follows that S is a strict subset of no other clique minimal separator associated with an edge of $\mu$, and as this holds for each inclusion-minimal clique minimal separator associated with an edge of $\mu$, the clique minimal separators associated with the edges of $\mu$ are pairwise non-inclusive and therefore all inclusion-minimal. Hence, $\mu$ satisfies the second alternative of Property 9, and for each set of consecutive edges $XY$ and $YZ$ of $\mu$ associated with the same clique minimal separator S, $C_S\left(X\right)=C_S\left(Z\right)$. □

Example 1.

A graph and its atom graph having an induced $C_4$ satisfying the first alternative of Property 9 is shown in Figure 3 (the cycle $(A,D,C,F)$ is such a $C_4$). A graph and its atom graph having an induced $C_4$ satisfying the second alternative of Property 9 is shown in Figure 4 (the cycle $(A,B,E,D)$ is such a $C_4$). Note that in both cases, the graph is chordal and has a clique tree which is a path: the path $(A,B,C,D,E,F)$, for instance, in the first case, and $(A,B,C,D,E)$, for instance, in the second case. This contradicts the claim from [18] that any path of a clique tree of a chordal graph induces a chordal subgraph of its atom graph.

For each $k\ge 3$, the atom graph of the graph obtained from a k-sun by adding a vertex of degree 1 adjacent to x for each vertex x of the clique of size k has an induced $C_{2k}$ satisfying the second alternative of Property 9 (see Figure 2 for $k=3$).

Corollary 1.

Each atom graph is odd-hole-free.

Property 10.

Each atom graph is anti-hole-free.

Proof. 

We assume for contradiction that some induced subgraph of some atom graph G is an anti-hole and let k be its length. $k\ge 6$ by Corollary 1 since an anti-hole of length 5 is a hole. Let $G^{\prime }$ be a graph such that G is isomorphic to $AG\left(G^{\prime }\right)$, let $\mu$ be a chordless cycle of $\overline{AG\left(G^{\prime }\right)}$ of length k, and let $(A^{\prime },A,D_1,B_1,B_2)$ be a sequence of consecutive nodes of $\mu$. As $k\ge 6$$\{A^{\prime },A,B_1,B_2\}$ induces a $C_4$ of $AG\left(G^{\prime }\right)$, so by Property 9 $A\cap B_1$ is equal to $A^{\prime }\cap B_1$ or to $A\cap B_2$. We assume without loss of generality that $A\cap B_1=A^{\prime }\cap B_1$. Let $(A^{\prime },A,D_1,B_1,\dots ,B_p,D_p)$ be the full sequence of consecutive vertices of $\mu$, and for each $i\in [1,p]$, let $S_i=A\cap B_i$ and let $P\left(i\right)$ be the predicate $S_i=A^{\prime }\cap B_i$. As $P\left(1\right)$ holds and for each $i\in [1,p-1]$, $P\left(i\right)\Rightarrow P(i+1)$ holds by Property 9, it follows by induction that $\forall i\in [1,p]$$P\left(i\right)$. Let $Y\in \{D_1,D_p\}$ and let $i\in \{1,p\}$. As $A{B}_i$ is an edge of $AG\left(G^{\prime }\right)$ $C_{S_i}\left(A\right)\ne C_{S_i}\left(B_i\right)$, and by Property 9 $C_{S_i}\left(A\right)=C_{S_i}\left(A^{\prime }\right)$. By Lemma 3 (c) with $\{X,X^{\prime }\}=\{A,A^{\prime }\}$, $C_{S_i}\left(A\right)=C_{S_i}\left(Y\right)$. It follows that $C_{S_i}\left(B_i\right)\ne C_{S_i}\left(Y\right)$, so by Lemma 3 (a) ($B_{i}Y$ is an edge of $AG\left(G^{\prime }\right)$⇔$N_{G^{\prime }}\left(C_{S_i}\left(Y\right)\right)\subseteq Y$). By Lemma 1 $S_i=N_{G^{\prime }}\left(C_{S_i}\left(A\right)\right)$, so $S_i=N_{G^{\prime }}\left(C_{S_i}\left(Y\right)\right)$, and therefore we have the equivalence ($B_{i}Y$ is an edge of $AG\left(G^{\prime }\right)$⇔$S_i\subseteq Y$). Hence $S_1⊈D_1$, $S_p\subseteq D_1$, $S_1\subseteq D_p$ and $S_p⊈D_p$. Let $x\in S_1\backslash D_1$ and let $y\in S_p\backslash D_p$. $x\in D_p\backslash D_1$, $y\in D_1\backslash D_p$ and $\{x,y\}\subseteq A\backslash (D_1\cap D_p)\subseteq C_{D_1\cap D_p}\left(A\right)$. Hence $D_1{D}_p$ is not an edge of $AG\left(G^{\prime }\right)$, a contradiction. □

Corollary 2.

Each atom graph is perfect.

5. Atom Graph and Clique Graph of a Chordal Graph

The atom graph of a chordal graph G is a subgraph of its clique graph with the same node set. These two graphs may be equal. It is the case if G is a block graph by Lemma 6 below, or the graph obtained from a $C_4$ by adding a chord, which is not a block graph. We have the following characterization.

Characterization 9.

Let G be a connected chordal graph. The following propositions are equivalent ($C_S\left(A\right)$ is defined in Notation 1):

• $AG\left(G\right)=CG\left(G\right)$,

• for each minimal separator S of G and each maximal clique A of G, $S\cap A=\varnothing$ or $N\left(C_S\left(A\right)\right)\subseteq A$,

• each cycle of $CG\left(G\right)$ has two edges that are of minimum weight among the edges of this cycle and are associated with the same set,

• each cycle of $CG\left(G\right)$ has two edges that are of minimum weight among the edges of this cycle.

Proof. 

Let T be a clique tree of G.

$1\Rightarrow 2$: let S be a minimal separator of G and let A be a maximal clique of G such that $S\cap A\ne \varnothing$. Let us show that $N\left(C_S\left(A\right)\right)\subseteq A$. Let $XY$ be an edge of T associated with S. As $C_S\left(X\right)\ne C_S\left(Y\right)$, at least one of them, say $C_S\left(X\right)$ is different from $C_S\left(A\right)$. Moreover, as $S\subseteq X$ and $S\cap A\ne \varnothing$, it follows that $X\cap A\ne \varnothing$. Hence, $XA$ is an edge of $CG\left(G\right)$, i.e., of $AG\left(G\right)$, so by item (a) of Lemma 3, $N\left(C_S\left(A\right)\right)\subseteq A$.

$2\Rightarrow 1$: as $AG\left(G\right)$ is a subgraph of $CG\left(G\right)$ with the same node set, it is sufficient to show that each edge of $CG\left(G\right)$ is an edge of $AG\left(G\right)$. Let $XY$ be an edge of $CG\left(G\right)$, and let us show that it is an edge of $AG\left(G\right)$. Let $Y^{\prime }$ be the neighbor of X on $P_T(X,Y)$ and let $S=X\cap Y^{\prime }$. As $XY$ is an edge of $CG\left(G\right)$ and $X\cap Y\subseteq S\cap Y$, it follows that $S\cap Y\ne \varnothing$, and therefore $N\left(C_S\left(Y\right)\right)\subseteq Y$. As X and Y are in different connected components of $T-\left\{X{Y}^{\prime }\right\}$, $C_S\left(X\right)\ne C_S\left(Y\right)$ [15], so by item (a) of Lemma 3 again $XY$ is an edge of $AG\left(G\right)$.

$1\Rightarrow 3$ immediately follows from Property 7.

$3\Rightarrow 4$ is evident.

$4\Rightarrow 1$: we assume for contradiction that $AG\left(G\right)\ne CG\left(G\right)$. Let $XY$ be an edge of $CG\left(G\right)$ that is not an edge of $AG\left(G\right)$. Then, by Characterization 5 for each edge $X^{\prime }{Y}^{\prime }$ of $P_T(X,Y)$$X\cap Y\subset X^{\prime }\cap Y^{\prime }$. Hence, $XY$ is the unique edge of minimum weight of the cycle of $CG\left(G\right)$ formed by $XY$ and $P_T(X,Y)$, a contradiction. □

We immediately refind from Characterization 9 that a block graph has the same atom and clique graph since it satisfies item 2. If G is not chordal then its atom graph is necessarily different from its clique graph since its atoms are not its maximal cliques (a chordless cycle of length at least 4 is connected and has no clique separator, and therefore is a subset of some atom). However, Characterization 9 extends to each connected graph, replacing ‘CG(G)’ by ‘the intersection graph of the set of atoms of G’, ‘minimal separator’ by ‘clique minimal separator’ and ‘maximal clique’ by ‘atom’ by Property 3.

These classes are inclusion-uncomparable. The 3-sun is an atom graph (it is the atom graph of the graph shown in Figure 5).

However, by Characterization 6 it is not a clique graph of a chordal graph (if it had a spanning tree T such that each maximal clique induces a subtree of T then each one of the three external triangles of the 3-sun would induce a subtree of T, and therefore T would have a cycle). Conversely, the non-perfect clique graph of a chordal graph shown in Figure 1 is not an atom graph since atom graphs are perfect. It follows that no necessary (resp. sufficient) condition for a graph to be a clique graph of a chordal graph immediately extends to atom graphs. We will go further into the comparison of these two classes in Section 7.

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 α-acyclic hypergraph such that G is isomorphic to $tuj\left(T\right)$.

Let H be a connected $\alpha$-acyclic hypergraph. By Property 6 there is a connected chordal graph G such that $UJ\left(H\right)=AG\left(G\right)$ and $L\left(H\right)=CG\left(G\right)$ up to some isomorphism. It follows that $UJ\left(H\right)$ is a subgraph of $L\left(H\right)$ 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 α-acyclic hypergraph. The following propositions are equivalent:

• $UJ\left(H\right)=L\left(H\right)$,

• each cycle of $L\left(H\right)$ has two edges that are of minimum weight among the edges of this cycle and are associated with the same set,

• each cycle of $L\left(H\right)$ 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 anexpanded treeif 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,\dots ,e_p)$ of the edges of T and $S_V$ is a sequence $(V_1,\dots ,V_p)$ of subsets of V such that for each $i,j\in [1,p]$, $T\left(V_i\right)$ is a subtree of T containing the edge $e_i$ and if $e_j$ is an edge of $T\left(V_i\right)$ then $j\ge 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,\dots ,e_p)$ of the edges of P and $S_V$ is the sequence $(V_1,\dots ,V_p)$ such that for each i from 1 to p$V_i$ is the union of the edges $e_j$, $j\ge i$. Hence, according to Characterization 13 below, trees and complete graphs are atom graphs, which also follows from Characterization 14.

Characterization 13.

A connected graph is an atom graph if and only if it is an AG-expanded tree.

To prove Characterization 13, we will use the following Lemma.

Lemma 4.

Let T be a join tree of a connected hypergraph, let X, Y be distinct nodes of T and let $X_m{Y}_m$ be an edge of $P_T(X,Y)$ whose associated set is inclusion-minimal among the sets associated with the edges of $P_T(X,Y)$. Then, $XY$ is an edge of $tuj\left(T\right)$ if and only if $X\cap Y=X_m\cap Y_m$ (or equivalently $X_m\cap Y_m\subseteq X\cap Y$).

Proof. 

We assume that $XY$ is an edge of $tuj\left(T\right)$. Let $X^{\prime }{Y}^{\prime }$ be an edge of $P_T(X,Y)$ such that $X\cap Y=X^{\prime }\cap Y^{\prime }$. As $X\cap Y\subseteq X_m\cap Y_m$ and $X\cap Y=X^{\prime }\cap Y^{\prime }\not\subset X_m\cap Y_m$, $X\cap Y=X_m\cap Y_m$. The converse implication is evident. □

Proof. 

(of Characterization 13) By Characterization 10 it is sufficient to show that there is a join tree T of a connected $\alpha$-acyclic hypergraph such that G is isomorphic to $tuj\left(T\right)$ if and only if G is an AG-expanded tree.

⇒: let T be a join tree of a connected hypergraph such that G is isomorphic to $tuj\left(T\right)$. It is sufficient to show that $tuj\left(T\right)$ is an AG-expanded tree. Let $S_e=(e_1=X_1{Y}_1,\dots ,e_p=X_p{Y}_p)$ be an ordering of the edges of T ordered by increasing weight, and let $S_V=(V_1,\dots ,V_p)$ where $V_i$ is the connected component of $T\left({\mathcal{E}}_{S_i}\right)-\{e_j,1\le j<i\}$ containing $e_i$, ${\mathcal{E}}_{S_i}$ being the set of nodes of T containing $S_i=X_i\cap Y_i$, for each $i\in [1,p]$. Let us show that $(T,S_e,S_V)$ is an AG-structure of $tuj\left(T\right)$. T is a spanning tree of $tuj\left(T\right)$. Let $i,j\in [1,p]$. By definition of $V_i$, $T\left(V_i\right)$ is a subtree of T containing the edge $e_i$ and if $e_j$ is an edge of $T\left(V_i\right)$ then $j\ge i$ and $V_j\subseteq V_i$ (as $e_j\subseteq V_i$, $S_i\subseteq X_j\cap Y_j=S_j$). Let $\{X,Y\}$ be a pair of nodes of T, and let $i=min\{j\in [1,p],$$e_j$$is$$an$$edge$$of$$P_T(X,Y)\}$. Let us show that $XY$ is an edge of $tuj\left(T\right)$ if and only if $\{X,Y\}\subseteq V_i$. By Lemma 4 and the definition of i, $XY$ is an edge of $tuj\left(T\right)$ if and only if $S_i\subseteq X\cap Y$, which is still equivalent to $\{X,Y\}\subseteq V_i$ since $T\left({\mathcal{E}}_{S_i}\right)$ is connected and for each edge $e_j$ of $P_T(X,Y)$, $j\ge i$. Hence, $(T,S_e,S_v)$ is an AG-structure of $tuj\left(T\right)$, which implies that $tuj\left(T\right)$ it is an AG-expanded tree.

⇐: let $G=(V,E)$ and let $(T,S_e,S_V)$ be an AG-structure of G, with $S_e=(e_1=x_1{y}_1,\dots ,e_p=x_p{y}_p)$ and $S_V=(V_1,\dots ,V_p)$. Let H be the hypergraph $(V^{\prime },\mathcal{E})$ where $V^{\prime }=V+\{v_1,\dots ,v_p\}$ and $\mathcal{E}=\{A_x$, $x\in V\}$, with $A_x=\left\{x\right\}+\{v_i$, $i\in [1,p]\wedge x\in V_i\}$. Let f map each vertex x of G to the hyperedge $A_x$ of H, and let $T^{\prime }=f\left(T\right)$. As $T\left(V_i\right)$ is a subtree of T for each $i\in [1,p]$, $T^{\prime }$ is a join tree of H, and as no edge of $T^{\prime }$ is associated with the empty set (the set associated with $f\left(e_i\right)$ contains at least $v_i$ since $e_i$ is an edge of $T\left(V_i\right)$), H is connected.

Let us show that G is isomorphic to $tuj\left(T^{\prime }\right)$. Let $\{x,y\}\subseteq V$. Let us show that $xy$ is an edge of G if and only if $A_x{A}_y$ is an edge of $tuj\left(T^{\prime }\right)$. Let $i=min\{j\in [1,p]$, $$$is$$an$$edge$$of$$P_T(x,y)\}$. 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\left(T^{\prime }\right)$. We assume that $\{x,y\}\subseteq V_i$. Let us show that $A_x{A}_y$ is an edge of $tuj\left(T^{\prime }\right)$. It is sufficient to show that $A_{x_i}\cap A_{y_i}\subseteq A_x\cap A_y$. 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\left(V_j\right)$, $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$. Conversely, we assume that $A_x{A}_y$ is an edge of $tuj\left(T^{\prime }\right)$. 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_j}$. As $e_j$ is an edge of $T\left(V_j\right)$, $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\left(V_j\right)$ is a subtree of T, $e_i$ is an edge of $T\left(V_j\right)$ and therefore $i\ge j$. As $i\le j$ by definition of i, $i=j$ and therefore $\{x,y\}\subseteq V_i$. Hence, G is isomorphic to $tuj\left(T^{\prime }\right)$. □

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\left(G^{\prime }\right)$ from an AG-structure $(T,S_e=(e_1,\dots ,e_p),S_V=(V_1,\dots ,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 }=2SEC\left(H\right)$ having $T^{\prime }$ as a clique tree. Note that $G^{\prime }$ can be defined from the set $\{V_1,\dots ,V_p\}$ alone: $G^{\prime }=(V^{\prime },E^{\prime })$, with $V^{\prime }=V+\{v_1,\dots ,v_p\}$ and $E^{\prime }=\{x{v}_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\ne \varnothing \}$.

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\left(G^{\prime }\right)$ 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).

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.

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\left(G^{\prime }\right)$. $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\left(V_i\right)$, $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\left(V_i\right)$, and therefore $j\ge i$. Symetrically $i\ge 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\left(m^{n-1}{n}^5\right)$ time. Whereas the number of graphs having $2n-1$ given vertices is $2^{(2n-1)(2n-2)/2}$, i.e.,${\left(2^{2n-1}\right)}^{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\left(m^{n-1}{n}^5\right)$ 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 ${(}_{n-1}^m)$ 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\left(n\right)$ time, this process is in $O\left(n{(}_{n-1}^m)\right)$ time, and therefore in $O(n{m}^{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\left(n\right)$ time, this process is in $O\left(n\right(n-1)!)$ time.

Now, given a spanning tree T and an ordering $(e_1,\dots ,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 connexity takes $O\left(n\right)$ time, and therefore $O\left(n^2\right)$ time for all i. If $e_j$ is an edge of $T\left(V_i\right)$ then necessarily $j\ge i$, and checking that $V_j\subseteq V_i$ takes $O\left(n\right)$ time, and therefore $O\left(n^3\right)$ 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\left(n^2\right)$ 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(n{m}^{n-1}/(n-1)!\ast n(n-1)!)\ast n^3)$ time, i.e., in $O\left(m^{n-1}{n}^5\right)$ time. □

We use Characterization 13 to show that the k-sun is not an atom graph if $k\ge 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\ge 4$ such that the k-sun is an atom graph.

Proof. 

We assume for contradiction that there is an integer $k\ge 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,\dots ,e_p),(V_1,\dots ,V_p))$ be an AG-structure of G. Let C be the clique of G of size k, let $D=V\backslash 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\left(C_2\right)$ is a subtree of T. Let $i_0=min\{i\in [1,p],$$e_i$$is$$an$$edge$$of$$T\left(C_2\right)\}$, let $e_{i_0}=x_1{x}_2$, and for each $i\in \{1,2\}$ let $X_i$ be the connected component of T-$\left\{e_{i_0}\right\}$ 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\}$. As $T\left(C_2\right)$ is a subtree of T, $P_T(x,y_j)$ is a path in $T\left(C_2\right)$, so $i_0=min\{i\in [1,p],$$e_i$$is$$an$$edge$$of$$P_T(x,y_j)\}$. As $x{y}_j$ is an edge of G, $x\in V_{i_0}$. Hence, $C\subseteq V_{i_0}$. As $T\left(V_{i_0}\right)$ is connected and each vertex of $D_2$ is on the path in T between its two neighbors which belong to C and therefore to $V_{i_0}$, $C_2\subseteq V_{i_0}$.

Let us show that for any triangle $(c,c^{\prime },d)$ in G such that $d\in D_1\backslash V_{i_0}$, there is an integer j in $[1,p]$ such that $V_j=e_j=c{c}^{\prime }$. Let $(c,c^{\prime },d)$ be such a triangle. We assume w.l.o.g. that c is the neighbor of d in T. Let $i=min\{r\in [1,p],$$e_r$$is$$an$$edge$$of$$P_T(c^{\prime },d)\}$. As $c^{\prime }d$ is an edge of G, $\{c^{\prime },d\}\subseteq V_i$. It follows that $e_i=cd$ (otherwise $e_i$ would be a subset of $C_2$, and therefore an edge of $T\left(V_{i_0}\right)$, so $V_i$ would be a subset of $V_{i_0}$ and would not contain d). Hence, d is adjacent to each vertex of $V_i\backslash \left\{d\right\}$, so $V_i=\{c,c^{\prime },d\}$ and $c{c}^{\prime }$ is an edge of T. Let j be the integer such that $c{c}^{\prime }=e_j$. As $e_j$ is an edge of $T\left(V_i\right)$, $V_j\subseteq V_i$ and as $V_j$ contains the edge $e_j$, but not the edge $e_i$ since $i<j$, $V_j=e_j$.

Now, as the vertices of D are pairwise non-adjacent in G, there is some $i\in \{1,2\}$ such that $D\cap V_{i_0}\subseteq X_i$. We assume without loss of generality that $i=1$. Then, $D\cap V_{i_0}\subseteq V_{i_0}\cap X_1\subseteq N_G\left(y_2\right)$. As G is a k-sun with $k\ge 4$, there are 2 triangles $(c,c_1,d_1)$ and $(c,c_2,d_2)$ such that for each $i\in \{1,2\}$, $d_i$ is in $D\backslash N_G\left(y_2\right)$, and therefore in $D\backslash V_{i_0}$, which is equal to $D_1\backslash V_{i_0}$ since $D_2\subseteq V_{i_0}$. So by the preceding argument, for each $i\in \{1,2\}$ there is an integer $j_i$ in $[1,p]$ such that $V_{j_i}=e_{j_i}=c{c}_i$. Hence, there is no integer r such that $e_r$ is an edge of $P_T(c_1,c_2)$ and $\{c_1,c_2\}\subseteq V_r$, and therefore $c_1{c}_2$ is not an edge of G, a contradiction. □

We showed in Section 5 that by Characterization 6 the 3-sun is not a clique graph of a chordal graph. The same argument holds for each $k\ge 3$: there is no integer k such that the k-sun is a clique graph of a chordal graph. However, the k-sun is a join-path-expanded tree for each $k\ge 3$: it is easy to check that any spanning tree T of the k-sun which is a spanning tree of the union of its external triangles such that each vertex of degree 2 in the k-sun is of degree 1 in T is a join-path spanning tree of the k-sun. A join-path spanning tree of the 4-sun is shown in Figure 8 (its edges are represented by full lines). It follows that the union of the classes of atom graphs and clique graphs of chordal graphs is a strict subclass of the class of join-path-expanded graphs.

8. Atom Graph Subclasses

8.1. Atom Graphs of ${\mathcal{G}}_{ninc}$

Notation 2.

${\mathcal{G}}_{ninc}$ denotes the class of graphs whose clique minimal separators are pairwise non-inclusive ($ninc$ stands for non-inclusive).

Equivalently, ${\mathcal{G}}_{ninc}$ is the class of graphs whose clique minimal separators have only full components (since the minimal separators that are subsets of a minimal separator S in a connected graph G are the neighborhoods of the connected components of $G(V\backslash S)$). We recall that a block graph is a chordal graph whose minimal separators are of size 1. Each block graph is in ${\mathcal{G}}_{ninc}$. As announced in Section 4, the atom graph of a graph of ${\mathcal{G}}_{ninc}$ is necessarily chordal. Moreover, it is a block graph and is an atom graph of a block graph.

Characterization 14.

Let G be a connected graph. The following propositions are equivalent.

• G is an atom graph of a graph of ${\mathcal{G}}_{ninc}$,

• G is a block graph,

• G is an atom graph of a block graph,

• G is a clique graph of a block graph,

To prove Characterization 14 we will use the following results. We first recall a characterization of the edges of the atom graph that are associated with a given clique minimal separator.

Characterization 15

([21]). Let G be a connected graph, let T be an atom tree of G and let S be a minimal separator of G. Then the edges of $AG\left(G\right)$ associated with S are the pairs of nodes of T whose endpoints are in different connected components of $T\left({\mathcal{A}}_S\right)-E_S$, where ${\mathcal{A}}_S$ is the set of nodes of T containing S and $E_S$ is the set of edges of T associated with S.

Lemma 5.

Let G be a connected graph of ${\mathcal{G}}_{ninc}$. Then $AG\left(G\right)$ is a block graph, and if G has at least two atoms then the maximal cliques of $AG\left(G\right)$ are the sets ${\mathcal{A}}_S$ of atoms of G containing S for each clique minimal separator S of G, and each edge in the clique ${\mathcal{A}}_S$ is associated with S.

Proof. 

If G has a unique atom then $AG\left(G\right)$ is clearly a block graph.

We assume now that G has at least two atoms. Let S be a clique minimal separator of G, let T be an atom tree of G, and let ${\mathcal{A}}_S$ and $E_S$ be defined as in Characterization 15. As the edges of $T\left({\mathcal{A}}_S\right)$ are associated with clique minimal separators containing S and $G\in {\mathcal{G}}_{ninc}$, all the edges of $T\left({\mathcal{A}}_S\right)$ are in $E_S$. It follows from Characterization 15 that ${\mathcal{A}}_S$ is a clique of $AG\left(G\right)$ and each edge in ${\mathcal{A}}_S$ is associated with S. Hence, to show that the maximal cliques of $AG\left(G\right)$ are the sets ${\mathcal{A}}_S$, it is sufficient to show that each element of $\mathcal{K}\left(AG\right(G\left)\right)$ is a subset of ${\mathcal{A}}_S$ for some clique minimal separator S. Let $\mathcal{K}\in \mathcal{K}\left(AG\right(G\left)\right)$. As G has at least two atoms $\left|\mathcal{K}\right|\ge 2$. Let $\{X,Y\}\subseteq \mathcal{K}$ and let $S=X\cap Y$. Let us show that $\mathcal{K}\subseteq {\mathcal{A}}_S$. Let $Z\in \mathcal{K}$. Let us show that $Z\in {\mathcal{A}}_S$. It is evident if $Z\in \{X,Y\}$. Otherwise by Property 8 and the fact that $G\in {\mathcal{G}}_{ninc}$, the three edges of the triangle $(X,Y,Z)$ are associated with S, and therefore $Z\in {\mathcal{A}}_S$. Hence $\mathcal{K}\subseteq {\mathcal{A}}_S$. Hence, the maximal cliques of $AG\left(G\right)$ are the sets ${\mathcal{A}}_S$ for each clique minimal separator S.

Let us show that $AG\left(G\right)$ is chordal. Let $\mu$ be a cycle in $AG\left(G\right)$ of length $\ge 4$. By Property 7 two edges of $\mu$ are associated with the same set S, which are contained in the clique ${\mathcal{A}}_S$ of $AG\left(G\right)$. Hence, $\mu$ has a chord, and therefore $AG\left(G\right)$ is chordal. It follows that each minimal separator of $AG\left(G\right)$ is the intersection of two maximal cliques of $AG\left(G\right)$, and therefore is of size 1 since otherwise, there would be a pair $\{S,S^{\prime }\}$ of clique minimal separators of G and an edge of $AG\left(G\right)$ in ${\mathcal{A}}_S\cap {\mathcal{A}}_{S^{\prime }}$ which would be associated with both S and $S^{\prime }$. It follows that $AG\left(G\right)$ is a block graph. □

Lemma 6.

For each connected block graph G, $AG\left(G\right)=CG\left(G\right)$.

Proof. 

As G is chordal, $AG\left(G\right)$ is a subgraph of $CG\left(G\right)$ with the same node set. Let us show that each edge of $CG\left(G\right)$ is an edge of $AG\left(G\right)$. Let $XY$ be an edge of $CG\left(G\right)$, let T be an atom tree of G and let $X^{\prime }{Y}^{\prime }$ be an edge of $P_T(X,Y)$. As $1\le |X\cap Y|\le |X^{\prime }\cap Y^{\prime }|=1$ with $X\cap Y\subseteq X^{\prime }\cap Y^{\prime }$, it follows that $X\cap Y=X^{\prime }\cap Y^{\prime }$, and therefore $XY$ is an edge of $AG\left(G\right)$ by Characterization 5. □

To prove that a block graph is an atom graph of a block graph, or equivalently by Lemma 6, a clique graph of a block graph, we will use a well-known technique allowing to compute a chordal graph whose clique graph is isomorphic to a given graph.

Notation 3.

For each graph $G=(V,E)$, $RetroCG\left(G\right)$ denotes the intesection graph of the set $\mathcal{K}\left(G\right)\cup \left\{\right\{x\},x\in V\}$.

Lemma 7.

Let $G=(V,E)$ be a connected graph, and let $G^{\prime }=RetroCG\left(G\right)$. If $CG\left(G\right)$ is chordal and for each maximal clique $\mathcal{K}$ of $CG\left(G\right)$, the elements of $\mathcal{K}$ have a non-empty intersection then $G^{\prime }$ is chordal, G is isomorphic to $CG\left(G^{\prime }\right)$ and the maximal cliques of $G^{\prime }$ are the sets $N_{G^{\prime }}\left[\left\{x\right\}\right]$ for each element x of V.

Proof. 

We recall the following properties of $RetroCG\left(G\right)$, which are easy to check:

(1) For each $x\in V$, $N_{G^{\prime }}\left[\left\{x\right\}\right]$ is a maximal clique of $G^{\prime }$,

(2) For each $\{x,y\}\subseteq V$$xy$ is an edge of G if and only if $N_{G^{\prime }}\left[\left\{x\right\}\right]\cap N_{G^{\prime }}\left[\left\{y\right\}\right]\ne \varnothing$,

(3) If for each maximal clique $\mathcal{K}$ of $CG\left(G\right)$, the elements of $\mathcal{K}$ have a non-empty intersection then the maximal cliques of $G^{\prime }$ are the sets $N_{G^{\prime }}\left[\left\{x\right\}\right]$ for each element x of V,

(4) $CG\left(G\right)$ is chordal if and only if $G^{\prime }$ is chordal.

It follows from these properties that under the hypothesis of the lemma, $G^{\prime }$ is chordal, and the mapping associating each vertex x of G with $N_{G^{\prime }}\left[\left\{x\right\}\right]$ is an isomorphism from G to $CG\left(G^{\prime }\right)$. □

Lemma 8.

Let $G=(V,E)$ be a connected block graph, and let $G^{\prime }=RetroCG\left(G\right)$. Then $G^{\prime }$ is a block graph and G is isomorphic to $CG\left(G^{\prime }\right)$.

Proof. 

By Lemma 6 $CG\left(G\right)=AG\left(G\right)$, so by Lemma 5 $CG\left(G\right)$ is chordal. Let $\mathcal{K}$ be a maximal clique of $CG\left(G\right)$, let us show that the elements of $\mathcal{K}$ have a non-empty intersection. If G has a unique atom then it is trivial, otherwise by Lemma 5 again it is the case since all the elements of $\mathcal{K}$ contain a given clique minimal separator S of G. Hence, by Lemma 7 $G^{\prime }$ is chordal, G is isomorphic to $CG\left(G^{\prime }\right)$ and the maximal cliques of $G^{\prime }$ are the sets $N_{G^{\prime }}\left[\left\{x\right\}\right]$ for each element x of V. Let us show that each minimal separator of $G^{\prime }$ is of size 1. We assume for contradiction that it is not the case. Then, there is a pair $\{x,y\}$ of V and a pair $\{K,L\}$ of $\mathcal{K}\left(G\right)$ in $N_{G^{\prime }}\left[\left\{x\right\}\right]\cap N_{G^{\prime }}\left[\left\{y\right\}\right]$, i.e., such that $\{x,y\}\subseteq K\cap L$. It follows that $KL$ is an edge of $CG\left(G\right)$, i.e., of $AG\left(G\right)$, and therefore is associated with a minimal separator of G of size at least 2, which contradicts the fact that G is a block graph. Hence, $G^{\prime }$ is a block graph. □

Proof. 

(of Characterization 14) $1\Rightarrow 2$ follows from Lemma 5, $2\Rightarrow 4$ follows from Lemma 8, $4\Rightarrow 3$ follows from Lemma 6, and $3\Rightarrow 1$ is evident. □

Example 4.

The 5-sun shown in Figure 1 is a graph of ${\mathcal{G}}_{ninc}$ and its atom graph is a block graph, with $\left\{F\right\}$ as unique minimal separator. Let G be this atom graph and let $G^{\prime }=RetroCG\left(G\right)$. The 5-sun, G and $G^{\prime }$ are shown in Figure 9. $G^{\prime }$ is a block graph whose atom graph is isomorphic to G. Note that G is also isomorphic to the atom graph of $G^{\prime }-\left\{F\right\}$, as the presence in $G^{\prime }$ of the node $\left\{F\right\}$ is not necessary since $N_{G^{\prime }}\left(\left\{F\right\}\right)$ is already a maximal clique of $G^{\prime }$.

The graph shown in Figure 2 is not a graph of ${\mathcal{G}}_{ninc}$. Its atom graph is not a block graph, and is isomorphic to the atom graph of no graph of ${\mathcal{G}}_{ninc}$ by Characterization 14.

It follows that block graphs, and in particular trees and complete graphs, are atom graphs. We have the following complexity results.

Lemma 9.

Let G be a connected block graph. Then $RetroCG\left(G\right)$ can be computed on $O\left(n^2\right)$ time.

Proof. 

Let $G^{\prime }=RetroCG\left(G\right)$. Its node set is computed in linear time since G is chordal. The edges of $G^{\prime }$ that are incident to a node of size 1 are computed in linear time too by scanning the maximal cliques of G, as the sum of their sizes is bounded by $n+m$. The other edges are computed by making $N_{G^{\prime }}\left(\left\{v\right\}\right)$ into a clique for each vertex v of G. Each edge is added only once by this process since two distinct non-disjoint maximal cliques of G have exactly one vertex in common since, by Lemma 6, their intersection is a minimal separator of G and G is a block graph. So this process takes $O\left(n^2\right)$ time, as G has at most n maximal cliques, and therefore $G^{\prime }$ is computed in $O\left(n^2\right)$ time. □

Theorem 2.

Recognition of an atom graph of a graph of ${\mathcal{G}}_{ninc}$ takes linear time, and if it is the case then a block graph whose atom graph is isomorphic to the input graph can be computed on $O\left(n^2\right)$ time.

Proof. 

The first result results from Characterization 14 and the fact that recognizing a block tree takes linear time. The second one results from Lemmas 6, 8 and 9. □

A block graph can be the atom graph of a graph not belonging to ${\mathcal{G}}_{ninc}$. For instance, if G is the chordal graph whose maximal cliques are $\{1,2,3\}$, $\{1,2,4\}$, and $\{1,5\}$, its minimal separators are $\{1,2\}$, and $\left\{1\right\}$, so G is not in ${\mathcal{G}}_{ninc}$ but its atom graph is a block graph since it is a complete graph.

8.2. Atom Graphs of ${\mathcal{G}}_{ninc}^2$

Notation 4.

${\mathcal{G}}_{ninc}^2$ denotes the class of graphs whose clique minimal separators have exactly 2 components.

${\mathcal{G}}_{ninc}^2\subseteq {\mathcal{G}}_{ninc}$ since a minimal separator has at least two full components. Thus, ${\mathcal{G}}_{ninc}^2$ is the set of graphs of ${\mathcal{G}}_{ninc}$ whose clique minimal separators have exactly two full components.

The equivalence between items 1 and 3 of Characterization 16 is proved in [24] for chordal graphs.

Characterization 16.

Let G be a connected graph. The following propositions are equivalent.

• G is a graph of ${\mathcal{G}}_{ninc}^2$;

• $AG\left(G\right)$ is a tree;

• G has a unique atom tree;

• The sets associated with the edges of $AG\left(G\right)$ are pairwise distinct;

• Each minimal separator of G is a subset of exactly 2 atoms of G.

Proof. 

Let S be a clique minimal separator of G, let ${\mathcal{A}}_S$ be the set of atoms of G containing S, let T be a clique tree of G, and let $E_S$ (resp. $E_S^{\prime }$) be the set of edges of T (resp. $AG\left(G\right)$) associated with S. By Properties 1 and 3 the number of full components of S in G is equal to $|E_S|+1$.

$1\Rightarrow 5$: as $G\in {\mathcal{G}}_{ninc}$, each edge of $T\left({\mathcal{A}}_S\right)$ is in $E_S$, and as S has exactly two full components, $|E_S|=1$. Hence $T\left({\mathcal{A}}_S\right)$ has a unique edge, and therefore two nodes.

$5\Rightarrow 4$: each edge of $E_S^{\prime }$ is a subset of ${\mathcal{A}}_S$.

$4\Rightarrow 3$: As T is a subgraph of $AG\left(G\right)$ by Characterization 4, $E_S\subseteq E_S^{\prime }$ with $1\le |E_S|\le |E_S^{\prime }|=1$. Hence, $E_S=E_S^{\prime }$ for each S, and therefore $T=AG\left(G\right)$.

$3\Rightarrow 2$: it follows from Characterization 4.

$2\Rightarrow 1$: there is no clique minimal separator $S^{\prime }$ stricly containing S, otherwise by Characterization 15 there would be a triangle in $AG\left(G\right)$ whose edges are associated with $S^{\prime }$, S and S, respectively, and $|E_S|=1$, otherwise by Characterization 15 again there would be a triangle in $AG\left(G\right)$ whose edges are associated with S. As this holds for each S, $G\in {\mathcal{G}}_{ninc}$ and each clique minimal separator has exactly 2 full components, i.e., $G\in {\mathcal{G}}_{ninc}^2$. □

Characterization 17.

A connected graph is an atom graph of a graph of ${\mathcal{G}}_{ninc}^2$ if and only if it is a tree.

Proof. 

The implication from left to right follows from Characterization 16. The converse implication follows from the fact that by Characterization 14, a tree is an atom graph, and from Characterization 16. □

We deduce from Theorem 2 and Characterizations 16 and 17 the following corollary.

Corollary 5.

Recognition of an atom graph of a graph of ${\mathcal{G}}_{ninc}^2$ takes linear time, and if it is the case then a block graph of ${\mathcal{G}}_{ninc}^2$ whose atom graph is isomorphic to the input graph can be computed on $O\left(n^2\right)$ time.

Contrary to the block graphs which are the atom graphs of block graphs, the trees are not the atom graphs of trees. As a non-path tree has a vertex of degree at least 3, its atom graph has a clique of size at least 3 and therefore is not a tree. It follows that conversely, a non-path tree is not an atom graph of a tree since it is an atom graph of neither a path nor a non-path tree. We easily check that the paths are the atom graphs of paths (though a path may be the atom graph of a non-path graph) and that the paths are the trees of ${\mathcal{G}}_{ninc}^2$. Still contrary to blocks graphs which can be atom graphs of graphs not belonging to ${\mathcal{G}}_{ninc}$, a tree can only be an atom graph of a graph of ${\mathcal{G}}_{ninc}^2$ by Characterization 16.

9. Conclusions

We have studied several aspects of atom graphs and atom graph recognition. We proved that each atom graph is perfect, presented characterizations of atom graphs and investigated the relationship between atom graphs, or equivalently atom graphs of chordal graphs, and clique graphs of chordal graphs. We also proved that the atom graphs of the graphs of two graph classes can be recognized in linear time. However, we leave as an open question the complexity of atom graph recognition. We only proved that it is in NP with a complexity in $O\left(m^{n-1}{n}^5\right)$ time. This result follows from the characterization of an atom graph as an AG-expanded tree, which is inspired by the characterization of a clique graph of a chordal graph as an expanded tree. As this characterization of a clique graph of a chordal graph leads to a polynomial recognition algorithm, this polynomial algorithm may be a source of inspiration for polynomial atom graph recognition. On the other side, as the definition of an AG-expanded tree is significantly more complex than that of an expanded tree, it is also possible that atom graph recognition is NP-complete.

Author Contributions

Conceptualization, G.S. and A.B.; methodology, G.S. and A.B.; no software; validation, G.S.; formal analysis, G.S.; investigation, G.S. and A.B.; resources, A.B.; data curation, A.B.; writing—original draft preparation, G.S. and A.B.; writing—review and editing, G.S.; visualization, G.S.; supervision, G.S.; project administration, G.S.; no funding acquisition. All authors have read and agreed to the published version of the manuscript.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Figures

Figure 1. A chordal graph, its non-perfect clique graph and its chordal atom graph.

Figure 2. A chordal graph, its chordal clique graph and its non-chordal (but perfect) atom graph.

Figure 3. A graph and its atom graph having an induced [Forumla omitted. See PDF.] whose edges are associated with the same clique minimal separator S.

Figure 4. A graph and its atom graph having an induced [Forumla omitted. See PDF.] whose edges are associated with two distinct clique minimal separators ([Forumla omitted. See PDF.] and [Forumla omitted. See PDF.]).

Figure 5. The 3-sun is an atom graph.

Figure 6. An AG-expanded tree G and one of its AG-expanded structures.

Figure 7. Construction of a graph [Forumla omitted. See PDF.] such that G is isomorphic to [Forumla omitted. See PDF.] from an AG-structure of G.

Figure 8. The 4-sun is a join-path-expanded tree.

Figure 9. A graph of [Forumla omitted. See PDF.], its atom graph G, which is a block graph, and the block graph [Forumla omitted. See PDF.] whose atom graph is isomorphic to G.

References

1. Tarjan, R.E. Decomposition by clique separators. Discret. Math.; 1985; 55, pp. 221-232. [DOI: https://dx.doi.org/10.1016/0012-365X(85)90051-2]

2. Leimer, H.-G. Optimal decomposition by clique separators. Discret. Math.; 1993; 113, pp. 99-123. [DOI: https://dx.doi.org/10.1016/0012-365X(93)90510-Z]

3. Berry, A.; Pogorelcnik, R.; Simonet, G. An introduction to clique minimal separator decomposition. J. Algorithms; 2010; 3, pp. 197-215. [DOI: https://dx.doi.org/10.3390/a3020197]

4. Coudert, D.; Ducoffe, G. Clique-decomposition revisited. [Research Report] Sophia Antipolis INRIA-I3S, hal-01266147. 2016; Available online: https://hal.archives-ouvertes.fr/hal-01266147/file/clique-decomposition-revisited.pdf (accessed on 18 August 2022).

5. Berry, A.; Brandstädt, A.; Giakoumakis, V.; Maffray, F. Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds. Discret. Appl. Math.; 2015; 184, pp. 50-61. [DOI: https://dx.doi.org/10.1016/j.dam.2014.11.018]

6. Berry, A.; Wagler, A. Triangulation and clique separator decomposition of claw-free graphs. LNCS Lect. Notes Comput. Sci.; 2012; 7551, pp. 7-21.

7. Brandstädt, A.; Giakoumakis, V.; Maffray, F. Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences. Discret. Appl. Math.; 2012; 160, pp. 471-478. [DOI: https://dx.doi.org/10.1016/j.dam.2011.10.031]

8. Brandstädt, A.; Hoàng, C.T. On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem. Theoret. Comput. Sci.; 2007; 389, pp. 295-306. [DOI: https://dx.doi.org/10.1016/j.tcs.2007.09.031]

9. Brandstädt, A.; Le, V.B.; Mahfud, S. New applications of clique separator decomposition for the Maximum Weight Stable Set Problem. Theoret. Comput. Sci.; 2007; 370, pp. 229-239. [DOI: https://dx.doi.org/10.1016/j.tcs.2006.10.035]

10. Bruhn, H.; Saito, A. Clique or hole in claw-free graphs. J. Comb. Theory Ser. B; 2012; 102, pp. 1-13. [DOI: https://dx.doi.org/10.1016/j.jctb.2011.02.004]

11. Olesen, K.G.; Madsen, A.L. Maximal prime subgraph decomposition of Bayesian networks. IEEE Trans. Syst. Man Cybern. Part B Cybern.; 2002; 32, pp. 21-31. [DOI: https://dx.doi.org/10.1109/3477.979956]

12. Biha, M.D.; Kaba, B.; Meurs, M.-J.; SanJuan, E. Graph decomposition approaches for terminology graphs. MICAI 2007, Lecture Notes in Computer Science; Springer: Berlin/Heidelberg, Germany, 2007; Volume 4827, pp. 883-893.

13. Jachiet, P.-A.; Pogorelcnik, R.; Berry, A.; Lopez, P.; Bapteste, E. MosaicFinder: Identification of fused gene families in sequence similarity networks. Bioinformatics; 2013; 29, pp. 837-844. [DOI: https://dx.doi.org/10.1093/bioinformatics/btt049] [PubMed: https://www.ncbi.nlm.nih.gov/pubmed/23365410]

14. Kaba, B.; Pinet, N.; Lelandais, G.; Berry, A. Clustering gene expression data using graph separators. In Silico Biol.; 2007; 7, pp. 433-452. [PubMed: https://www.ncbi.nlm.nih.gov/pubmed/18391236]

15. Blair, J.R.S.; Peyton, B.W. An introduction to chordal graphs and clique trees. Graph Theory Sparse Matrix Comput.; 1993; 56, pp. 1-29.

16. Gavril, F. The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combin. Theory Ser. B; 1974; 16, pp. 47-56. [DOI: https://dx.doi.org/10.1016/0095-8956(74)90094-X]

17. Szwarcfiter, J.L.; Bornstein, C.F. Clique Graphs of Chordal and Path Graphs. SIAM J. Discrete Math.; 1994; 7, pp. 331-336. [DOI: https://dx.doi.org/10.1137/S0895480191223191]

18. Galinier, P.; Habib, M.; Paul, C. Chordal.graphs and their clique graphs. Graph Theoretic Concepts in Computer Science (WG’95), Lecture Notes in Computer Science; Springer: Berlin, Germany, 1995; Volume 1017, pp. 358-371.

19. Habib, M.; Stacho, J. Reduced clique graphs of chordal.graphs. Eur. J. Comb.; 2012; 33, pp. 712-735. [DOI: https://dx.doi.org/10.1016/j.ejc.2011.09.031]

20. Berry, A.; Pogorelcnik, R.; Simonet, G. Organizing the atoms of the clique separator decomposition into an atom tree. Discret. Appl. Math.; 2014; 177, pp. 1-13. [DOI: https://dx.doi.org/10.1016/j.dam.2014.05.030]

21. Berry, A.; Simonet, G. Computing the atom graph of a graph and the union join graph of a hypergraph. Algorithms; 2021; 14, 347. [DOI: https://dx.doi.org/10.3390/a14120347]

22. Dirac, G.A. On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg; 1961; 25, pp. 71-76. [DOI: https://dx.doi.org/10.1007/BF02992776]

23. Buneman, P. A characterization of rigid circuit graphs. Discret. Math.; 1974; 9, pp. 205-212. [DOI: https://dx.doi.org/10.1016/0012-365X(74)90002-8]

24. Kumar, P.S.; Madhavan, C.E.V. Clique tree generalization and new subclasses of chordal graphs. Discret. Appl. Math.; 2002; 117, pp. 109-131. [DOI: https://dx.doi.org/10.1016/S0166-218X(00)00336-X]

25. Brandstädt, A.; Dragan, F.F.; Chepoi, V.; Voloshin, V. Dually Chordal Graphs. SIAM J. Discrt. Math.; 1998; 11, pp. 437-455. [DOI: https://dx.doi.org/10.1137/S0895480193253415]

26. Alcón, L.; Faria, L.; Figueiredo, C.M.H.D.; Gutierez, M. The complexity of clique graph recognition. Theor. Comput. Sci.; 2009; 410, pp. 2072-2083. [DOI: https://dx.doi.org/10.1016/j.tcs.2009.01.018]