The matching extendability of optimal $1$-embedded graphs on the projective plane
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909456900554752 |
|---|---|
| author | Koizumi, Shohei Suzuki, Yusuke |
| author_facet | Koizumi, Shohei Suzuki, Yusuke |
| contents | In this paper, we discuss matching extendability of optimal $1$-projective plane graphs (abbreviated as O1PPG), which are drawn on the projective plane $P^2$ so that every edge crosses another edge at most once, and has $n$ vertices and exactly $4n- 4$ edges. We first show that every O1PPG of even order is $1$-extendable. Next, we characterize $2$-extendable O1PPG's in terms of a separating cycle consisting of only non-crossing edges. Moreover, we characterize O1PPG's having connectivity exactly $5$. Using the characterization, we further identify three independent edges in those graphs that are not extendable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_19074 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The matching extendability of optimal $1$-embedded graphs on the projective plane Koizumi, Shohei Suzuki, Yusuke Combinatorics In this paper, we discuss matching extendability of optimal $1$-projective plane graphs (abbreviated as O1PPG), which are drawn on the projective plane $P^2$ so that every edge crosses another edge at most once, and has $n$ vertices and exactly $4n- 4$ edges. We first show that every O1PPG of even order is $1$-extendable. Next, we characterize $2$-extendable O1PPG's in terms of a separating cycle consisting of only non-crossing edges. Moreover, we characterize O1PPG's having connectivity exactly $5$. Using the characterization, we further identify three independent edges in those graphs that are not extendable. |
| title | The matching extendability of optimal $1$-embedded graphs on the projective plane |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.19074 |