The Hereditary Closure of the Unigraphs
| Autor: | Barrus, Michael D., Trenk, Ann N., Whitman, Rebecca |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | A graph with degree sequence $\pi$ is a \emph{unigraph} if it is isomorphic to every graph that has degree sequence $\pi$. The class of unigraphs is not hereditary and in this paper we study the related hereditary class HCU, the hereditary closure of unigraphs, consisting of all graphs induced in a unigraph. We characterize the class HCU in multiple ways making use of the tools of a decomposition due to Tyshkevich and a partial order on degree sequences due to Rao. We also provide a new characterization of the class that consists of unigraphs for which all induced subgraphs are also unigraphs. Comment: 35 pages, 6 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|