Minimally tough series-parallel graphs with toughness at least $1/2$
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909938504171520 |
|---|---|
| author | Katona, Gyula Y. Khan, Humara |
| author_facet | Katona, Gyula Y. Khan, Humara |
| contents | Let $t$ be a positive real number. A graph is called \emph{$t$-tough} if the removal of any vertex set $S$ that disconnects the graph leaves at most $|S|/t$ components. The toughness of a graph is the largest $t$ for which the graph is $t$-tough. A graph is minimally $t$-tough if the toughness of the graph is $t$, and the deletion of any edge from the graph decreases the toughness. Series--parallel graphs are graphs with two distinguished vertices called
terminals, formed recursively by two simple composition operations, series
and parallel joins. They can be used to model series and parallel electric circuits.
We characterize the minimally $t$-tough series-parallel graphs for all $t\ge 1/2$. It is clear that there is no minimally $t$-tough series-parallel graph if $t>1$. We show that for $1\ge t >1/2$, most of the series-parallel graphs with toughness $t$ are minimally $t$-tough, but most of the series-parallel graphs with toughness $1/2$ are not minimally $1/2$-tough. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_01905 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimally tough series-parallel graphs with toughness at least $1/2$ Katona, Gyula Y. Khan, Humara Combinatorics Discrete Mathematics 05C40 Let $t$ be a positive real number. A graph is called \emph{$t$-tough} if the removal of any vertex set $S$ that disconnects the graph leaves at most $|S|/t$ components. The toughness of a graph is the largest $t$ for which the graph is $t$-tough. A graph is minimally $t$-tough if the toughness of the graph is $t$, and the deletion of any edge from the graph decreases the toughness. Series--parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations, series and parallel joins. They can be used to model series and parallel electric circuits. We characterize the minimally $t$-tough series-parallel graphs for all $t\ge 1/2$. It is clear that there is no minimally $t$-tough series-parallel graph if $t>1$. We show that for $1\ge t >1/2$, most of the series-parallel graphs with toughness $t$ are minimally $t$-tough, but most of the series-parallel graphs with toughness $1/2$ are not minimally $1/2$-tough. |
| title | Minimally tough series-parallel graphs with toughness at least $1/2$ |
| topic | Combinatorics Discrete Mathematics 05C40 |
| url | https://arxiv.org/abs/2512.01905 |