Covering the edges of a graph with perfect matchings
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916511369658368 |
|---|---|
| author | Silina, Olha |
| author_facet | Silina, Olha |
| contents | An $r$-graph is an $r$-regular graph with no odd cut of size less than $r$. A well-celebrated result due to Lovász says that for such graphs the linear system $Ax = \textbf{1}$ has a solution in $\mathbb{Z}/2$, where $A$ is the $0,1$ edge to perfect matching incidence matrix. Note that we allow $x$ to have negative entries. In this paper, we present an improved version of Lovász's result, proving that, in fact, there is a solution $x$ with all entries being either integer or $+1/2$ and corresponding to a linearly independent set of perfect matchings. Moreover, the total number of $+1/2$'s is at most $6k$, where $k$ is the number of Petersen bricks in the tight cut decomposition of the graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_10224 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Covering the edges of a graph with perfect matchings Silina, Olha Combinatorics 05C70 An $r$-graph is an $r$-regular graph with no odd cut of size less than $r$. A well-celebrated result due to Lovász says that for such graphs the linear system $Ax = \textbf{1}$ has a solution in $\mathbb{Z}/2$, where $A$ is the $0,1$ edge to perfect matching incidence matrix. Note that we allow $x$ to have negative entries. In this paper, we present an improved version of Lovász's result, proving that, in fact, there is a solution $x$ with all entries being either integer or $+1/2$ and corresponding to a linearly independent set of perfect matchings. Moreover, the total number of $+1/2$'s is at most $6k$, where $k$ is the number of Petersen bricks in the tight cut decomposition of the graph. |
| title | Covering the edges of a graph with perfect matchings |
| topic | Combinatorics 05C70 |
| url | https://arxiv.org/abs/2309.10224 |