Properties and Recognition of Atom Graphs
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 <i>G</i> is an atom graph if there is a graph whose atom graph is isomorphic to <i...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-08-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/15/8/294 |
| _version_ | 1797411656169422848 |
|---|---|
| author | Geneviève Simonet Anne Berry |
| author_facet | Geneviève Simonet Anne Berry |
| author_sort | Geneviève Simonet |
| collection | DOAJ |
| description | 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 <i>G</i> is an atom graph if there is a graph whose atom graph is isomorphic to <i>G</i>. 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. |
| first_indexed | 2024-03-09T04:49:17Z |
| format | Article |
| id | doaj.art-dc45d7d7ac6b4f729fe8bb77ac08f743 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-09T04:49:17Z |
| publishDate | 2022-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-dc45d7d7ac6b4f729fe8bb77ac08f7432023-12-03T13:12:28ZengMDPI AGAlgorithms1999-48932022-08-0115829410.3390/a15080294Properties and Recognition of Atom GraphsGeneviève Simonet0Anne Berry1LIRMM, 161 Rue Ada, F-34 392 Montpellier, FranceLIMOS UMR CNRS 6158, Ensemble Scientifique des Cézeaux, F-63 173 Aubière, FranceThe 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 <i>G</i> is an atom graph if there is a graph whose atom graph is isomorphic to <i>G</i>. 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.https://www.mdpi.com/1999-4893/15/8/294clique minimal separator decompositionatom treeatom graphclique graph of a chordal graphatom graph recognition |
| spellingShingle | Geneviève Simonet Anne Berry Properties and Recognition of Atom Graphs Algorithms clique minimal separator decomposition atom tree atom graph clique graph of a chordal graph atom graph recognition |
| title | Properties and Recognition of Atom Graphs |
| title_full | Properties and Recognition of Atom Graphs |
| title_fullStr | Properties and Recognition of Atom Graphs |
| title_full_unstemmed | Properties and Recognition of Atom Graphs |
| title_short | Properties and Recognition of Atom Graphs |
| title_sort | properties and recognition of atom graphs |
| topic | clique minimal separator decomposition atom tree atom graph clique graph of a chordal graph atom graph recognition |
| url | https://www.mdpi.com/1999-4893/15/8/294 |
| work_keys_str_mv | AT genevievesimonet propertiesandrecognitionofatomgraphs AT anneberry propertiesandrecognitionofatomgraphs |