Cubic graphs with edges in exactly one perfect matching
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916439315709952 |
|---|---|
| author | Goedgebeur, Jan Mattiolo, Davide Mazzuoccolo, Giuseppe Renders, Jarne Wolf, Isaak H. |
| author_facet | Goedgebeur, Jan Mattiolo, Davide Mazzuoccolo, Giuseppe Renders, Jarne Wolf, Isaak H. |
| contents | Petersen's seminal work in 1891 asserts that the edge-set of a cubic graph can be covered by distinct perfect matchings if and only if it is bridgeless. Actually, it is known that for a very large fraction of bridgeless cubic graphs, every edge belongs to at least two distinct perfect matchings. In this paper, we study the class of non-double covered cubic graphs, i.e.\ graphs having an edge, called lonely edge, which belongs to exactly one perfect matching. First of all, we provide a reduction of the problem to the subclass $\cal U$ of $3$-connected cubic graphs. Then, we furnish an inductive characterization of $\cal U$ and we study properties related to the count of lonely edges. In particular, denoting by $\mathcal{U}_k$ the subclass of graphs of $\cal U$ with exactly $k$ lonely edges, we prove that $\mathcal{U}_k$ is empty for $k>6$, and we present a complete characterization for $3 \leq k \leq 6$. The paper concludes with some insights on ${\cal U}_1$ and ${\cal U}_2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08538 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Cubic graphs with edges in exactly one perfect matching Goedgebeur, Jan Mattiolo, Davide Mazzuoccolo, Giuseppe Renders, Jarne Wolf, Isaak H. Combinatorics 05C75 Petersen's seminal work in 1891 asserts that the edge-set of a cubic graph can be covered by distinct perfect matchings if and only if it is bridgeless. Actually, it is known that for a very large fraction of bridgeless cubic graphs, every edge belongs to at least two distinct perfect matchings. In this paper, we study the class of non-double covered cubic graphs, i.e.\ graphs having an edge, called lonely edge, which belongs to exactly one perfect matching. First of all, we provide a reduction of the problem to the subclass $\cal U$ of $3$-connected cubic graphs. Then, we furnish an inductive characterization of $\cal U$ and we study properties related to the count of lonely edges. In particular, denoting by $\mathcal{U}_k$ the subclass of graphs of $\cal U$ with exactly $k$ lonely edges, we prove that $\mathcal{U}_k$ is empty for $k>6$, and we present a complete characterization for $3 \leq k \leq 6$. The paper concludes with some insights on ${\cal U}_1$ and ${\cal U}_2$. |
| title | Cubic graphs with edges in exactly one perfect matching |
| topic | Combinatorics 05C75 |
| url | https://arxiv.org/abs/2402.08538 |