Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2207.06891 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909672469954560 |
|---|---|
| author | Benedetti, Bruno Pavelka, Marta |
| author_facet | Benedetti, Bruno Pavelka, Marta |
| contents | For $d \ge 2$, we show that all graphs of $d$-polytopes have a Hamiltonian line graph if and only if $d \ne 3$: We exhibit a graph of a $3$-polytope on $252$ vertices whose line graph does not even have Hamiltonian paths. Adapting a construction by Grünbaum and Motzkin, for large $n$ we also construct simple $3$-polytopes on $3n$ vertices in whose line graph any simple path is shorter than $10 n^α$, for some constant $α<1$. Moreover, we give four elementary counterexamples of plausible extensions to simplicial complexes of four famous results in Hamiltonian graph theory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_06891 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Higher-dimensional counterexamples to Hamiltonicity Benedetti, Bruno Pavelka, Marta Combinatorics For $d \ge 2$, we show that all graphs of $d$-polytopes have a Hamiltonian line graph if and only if $d \ne 3$: We exhibit a graph of a $3$-polytope on $252$ vertices whose line graph does not even have Hamiltonian paths. Adapting a construction by Grünbaum and Motzkin, for large $n$ we also construct simple $3$-polytopes on $3n$ vertices in whose line graph any simple path is shorter than $10 n^α$, for some constant $α<1$. Moreover, we give four elementary counterexamples of plausible extensions to simplicial complexes of four famous results in Hamiltonian graph theory. |
| title | Higher-dimensional counterexamples to Hamiltonicity |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2207.06891 |