Cliques in realization graphs
| Autor: | Barrus, Michael D., Haronian, Nathan |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The realization graph $\mathcal{G}(d)$ of a degree sequence $d$ is the graph whose vertices are labeled realizations of $d$, where edges join realizations that differ by swapping a single pair of edges. Barrus [On realization graphs of degree sequences, Discrete Mathematics, vol. 339 (2016), no. 8, pp. 2146-2152] characterized $d$ for which $\mathcal{G}(d)$ is triangle-free. Here, for any $n \geq 4$, we describe a structure in realizations of $d$ that exactly determines whether $G(d)$ has a clique of size $n$. As a consequence we determine the degree sequences $d$ for which $\mathcal{G}(d)$ is a complete graph on $n$ vertices. Comment: 15 pages, 8 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|