2023/09/19 by Olha Silina, Silina, Olha
Computer Science · Engineering · Mathematics · #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2309.10224
openalex publication_date 2023/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 = 1 has a solution in ℤ/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.