On minimally tough chordal graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912469597814784 |
|---|---|
| author | Dallard, Clément Fernández, Blas Katona, Gyula Y. Milanič, Martin Varga, Kitti |
| author_facet | Dallard, Clément Fernández, Blas Katona, Gyula Y. Milanič, Martin Varga, Kitti |
| contents | Katona and Varga showed that for any rational number $t \in (1/2,1]$, no chordal graph is minimally $t$-tough, while Katona and Khan characterized all minimally $t$-tough, chordal graphs with $t \le 1/2$. We conjecture that no chordal graph is minimally $t$-tough for any $t>1$ and prove several results supporting the conjecture. In particular, we show that for any $t>1/2$, no strongly chordal graph is minimally $t$-tough%, no split graph is minimally $t$-tough, and no chordal graph with a universal vertex is minimally $t$-tough. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_00383 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On minimally tough chordal graphs Dallard, Clément Fernández, Blas Katona, Gyula Y. Milanič, Martin Varga, Kitti Combinatorics Discrete Mathematics 05C42 G.2.2 Katona and Varga showed that for any rational number $t \in (1/2,1]$, no chordal graph is minimally $t$-tough, while Katona and Khan characterized all minimally $t$-tough, chordal graphs with $t \le 1/2$. We conjecture that no chordal graph is minimally $t$-tough for any $t>1$ and prove several results supporting the conjecture. In particular, we show that for any $t>1/2$, no strongly chordal graph is minimally $t$-tough%, no split graph is minimally $t$-tough, and no chordal graph with a universal vertex is minimally $t$-tough. |
| title | On minimally tough chordal graphs |
| topic | Combinatorics Discrete Mathematics 05C42 G.2.2 |
| url | https://arxiv.org/abs/2210.00383 |