A note on maximal plane subgraphs of the complete twisted graph containing perfect matchings
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914507037605888 |
|---|---|
| author | Omaña-Pulido, Elsa Rivera-Campo, Eduardo |
| author_facet | Omaña-Pulido, Elsa Rivera-Campo, Eduardo |
| contents | The twisted graph $T_{n}$ is a drawing of the complete graph with $n$ vertices $v_{1},v_{2},\ldots ,v_{n}$ in which two edges $v_{i}v_{j}$ ($i<j$) and $v_{s}v_{t}$ ($s<t$) cross if and only if $i<s<t<j$ or $s<i<j<t$. We show that for any maximal plane subgraphs $S$ and $R$ of $T_{n}$, each containing at least one perfect matching, there is a sequence $S=F_0, F_1, \ldots, F_m=R$ of maximal plane subgrahs of $T_n$, also containing perfect matchings, such that for $i=0,1, \ldots, m-1$, $F_{i+1}$ can be obtained from $F_{i}$ by a single edge exchange. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_02711 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A note on maximal plane subgraphs of the complete twisted graph containing perfect matchings Omaña-Pulido, Elsa Rivera-Campo, Eduardo Combinatorics The twisted graph $T_{n}$ is a drawing of the complete graph with $n$ vertices $v_{1},v_{2},\ldots ,v_{n}$ in which two edges $v_{i}v_{j}$ ($i<j$) and $v_{s}v_{t}$ ($s<t$) cross if and only if $i<s<t<j$ or $s<i<j<t$. We show that for any maximal plane subgraphs $S$ and $R$ of $T_{n}$, each containing at least one perfect matching, there is a sequence $S=F_0, F_1, \ldots, F_m=R$ of maximal plane subgrahs of $T_n$, also containing perfect matchings, such that for $i=0,1, \ldots, m-1$, $F_{i+1}$ can be obtained from $F_{i}$ by a single edge exchange. |
| title | A note on maximal plane subgraphs of the complete twisted graph containing perfect matchings |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2507.02711 |