Minimal toughness in subclasses of weakly chordal graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910042372964352 |
|---|---|
| author | Gollin, J. Pascal Milanič, Martin Ogrin, Laura |
| author_facet | Gollin, J. Pascal Milanič, Martin Ogrin, Laura |
| contents | The toughness of a graph $G$ is defined as the largest real number $t$ such that for any set $S\subseteq V(G)$ such that $G-S$ is disconnected, $S$ has at least $t$ times more elements than $G-S$ has components (unless $G$ is complete, in which case the toughness is defined to be infinite). A graph is said to be minimally tough if deleting any edge decreases the toughness. It is an open question whether there exists a minimally tough non-complete chordal graph with toughness exceeding $1$. We initiate the study of minimally tough graphs in the larger class of weakly chordal graphs. We obtain complete classifications of minimally tough graphs in the following subclasses of weakly chordal graphs: co-chordal graphs whose complement has diameter at least $3$, net-free co-chordal graphs, complements of forests, $P_4$-free graphs, and complete multipartite graphs. Our approach leads to simple proofs of two results on minimally tough graphs due to Dallard, Fernández, Katona, Milanič, and Varga. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_05100 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Minimal toughness in subclasses of weakly chordal graphs Gollin, J. Pascal Milanič, Martin Ogrin, Laura Combinatorics Discrete Mathematics 05C42, 05C40, 05C70, 05C07, 05C38, 05C69 The toughness of a graph $G$ is defined as the largest real number $t$ such that for any set $S\subseteq V(G)$ such that $G-S$ is disconnected, $S$ has at least $t$ times more elements than $G-S$ has components (unless $G$ is complete, in which case the toughness is defined to be infinite). A graph is said to be minimally tough if deleting any edge decreases the toughness. It is an open question whether there exists a minimally tough non-complete chordal graph with toughness exceeding $1$. We initiate the study of minimally tough graphs in the larger class of weakly chordal graphs. We obtain complete classifications of minimally tough graphs in the following subclasses of weakly chordal graphs: co-chordal graphs whose complement has diameter at least $3$, net-free co-chordal graphs, complements of forests, $P_4$-free graphs, and complete multipartite graphs. Our approach leads to simple proofs of two results on minimally tough graphs due to Dallard, Fernández, Katona, Milanič, and Varga. |
| title | Minimal toughness in subclasses of weakly chordal graphs |
| topic | Combinatorics Discrete Mathematics 05C42, 05C40, 05C70, 05C07, 05C38, 05C69 |
| url | https://arxiv.org/abs/2603.05100 |