Planar cycle-extendable graphs
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_ | 1866916745486270464 |
|---|---|
| author | Dalwadi, Aditya Y Pause, Kapil R Shenvi Diwan, Ajit A Kothari, Nishad |
| author_facet | Dalwadi, Aditya Y Pause, Kapil R Shenvi Diwan, Ajit A Kothari, Nishad |
| contents | For most problems pertaining to perfect matchings, one may restrict attention to matching covered graphs - that is, connected nontrivial graphs with the property that each edge belongs to some perfect matching. There is extensive literature on these graphs that are also known as 1-extendable graphs (since each edge extends to a perfect matching) including an ear decomposition theorem due to Lovász and Plummer.
A cycle $C$ of a graph $G$ is conformal if $G-V(C)$ has a perfect matching; such cycles play an important role in the study of perfect matchings, especially when investigating the Pfaffian orientation problem. A matching covered graph $G$ is cycle-extendable if - for each even cycle $C$ - the cycle $C$ is conformal, or equivalently, each perfect matching of $C$ extends to a perfect matching of $G$, or equivalently, $C$ is the symmetric difference of two perfect matchings of $G$, or equivalently, $C$ extends to an ear decomposition of $G$. In the literature, these are also known as cycle-nice or as 1-cycle resonant graphs.
Zhang, Wang, Yuan, Ng and Cheng, 2022, provided a characterization of claw-free cycle-extendable graphs. Guo and Zhang, 2004, and independently Zhang and Li, 2012, provided characterizations of bipartite planar cycle-extendable graphs. In this paper, we establish a characterization of all planar cycle-extendable graphs - in terms of $K_2$ and four infinite families. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_15416 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Planar cycle-extendable graphs Dalwadi, Aditya Y Pause, Kapil R Shenvi Diwan, Ajit A Kothari, Nishad Combinatorics Discrete Mathematics For most problems pertaining to perfect matchings, one may restrict attention to matching covered graphs - that is, connected nontrivial graphs with the property that each edge belongs to some perfect matching. There is extensive literature on these graphs that are also known as 1-extendable graphs (since each edge extends to a perfect matching) including an ear decomposition theorem due to Lovász and Plummer. A cycle $C$ of a graph $G$ is conformal if $G-V(C)$ has a perfect matching; such cycles play an important role in the study of perfect matchings, especially when investigating the Pfaffian orientation problem. A matching covered graph $G$ is cycle-extendable if - for each even cycle $C$ - the cycle $C$ is conformal, or equivalently, each perfect matching of $C$ extends to a perfect matching of $G$, or equivalently, $C$ is the symmetric difference of two perfect matchings of $G$, or equivalently, $C$ extends to an ear decomposition of $G$. In the literature, these are also known as cycle-nice or as 1-cycle resonant graphs. Zhang, Wang, Yuan, Ng and Cheng, 2022, provided a characterization of claw-free cycle-extendable graphs. Guo and Zhang, 2004, and independently Zhang and Li, 2012, provided characterizations of bipartite planar cycle-extendable graphs. In this paper, we establish a characterization of all planar cycle-extendable graphs - in terms of $K_2$ and four infinite families. |
| title | Planar cycle-extendable graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2405.15416 |