Metraipolis › archive › dc_e578b4fdcd26
The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs — arXiv:2608.09869
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.09869
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T09:09:08.237Z
- SHA-256 of the archived text
da954dc95db79bf5dd3196c9da4aa124c86c59ed1943e794ec12a98d9c1a6c16- Stable URL of this page
https://metraipolis.com/documento/dc_e578b4fdcd26
How to cite
The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs — arXiv:2608.09869 — arXiv (en), https://arxiv.org/abs/2608.09869 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e578b4fdcd26 (Metraipolis archive dc_e578b4fdcd26, sha256 da954dc95db79bf5dd3196c9da4aa124c86c59ed1943e794ec12a98d9c1a6c16)
BibTeX
@misc{dce578b4fdcd26,
title = {The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs — arXiv:2608.09869},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.09869},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e578b4fdcd26; sha256 da954dc95db79bf5dd3196c9da4aa124c86c59ed1943e794ec12a98d9c1a6c16},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.09869. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A graph on \(n\) vertices is called a Parter graph if there exists a nonsingular symmetric matrix, whose nonzero off-diagonal entries correspond exactly to the edges of the graph, such that all of its principal submatrices of order \(n-1\) are singular. Previously, a graph satisfying this condition was said to have property~(P). It was proved that, for bipartite graphs of cycle rank at most \(3\), being a Parter graph is equivalent to the existence of a perfect matching. We extend this result to cycle rank \(4\), proving that every bipartite graph of cycle rank at most \(4\) is a Parter graph if and only if it has a perfect matching. Furthermore, we show that this bound is sharp by constructing, for every integer \(r\ge5\), a connected balanced bipartite Parter graph of cycle rank \(r\) that has no perfect matching. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in math.CO). Categorie arXiv: Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2608.09869 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-19T09:05:33.597Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).