The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.09869
curl -X POST /api/v1/records/arxiv/2608.09869/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.09869/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'