Non-double covered cubic graphs
| Autor: | Goedgebeur, Jan, Mattiolo, Davide, Mazzuoccolo, Giuseppe, Renders, Jarne, Wolf, Isaak H. |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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$. Comment: 20 pages, 17 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|