Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 42 min ago
PreprintCC BY 4.0arXiv

The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs

  • G. Arunkumar
  • Puja Samanta
Open at sourcePDFDOICite

Abstract

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≥5, a connected balanced bipartite Parter graph of cycle rank r that has no perfect matching.

Related

  1. Covering Bridgeless Claw-Free Cubic Graphs with Perfect Matchings
    Huaibin Zhou, Xiumei Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Exact local spectral thresholds for perfect matchings in $3$-graphs and $3$-partite $3$-graphs
    Pei Liu, Suil O
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Signless Laplacian spectral conditions for rainbow matchings in a collection of bipartite graphs
    Zhiwei Guo, Nanxi Pan, Li Li +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. A tris of perfect matchings in bridgeless claw-free cubic graphs
    Jean Paul Zerafa
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Perfect matchings in planar 3-connected graphs: girth five and minimum degree five
    Xinyu Dai
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{arunkumar2026cycle,
  title = {{The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs}},
  author = {G. Arunkumar and Puja Samanta},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.09869},
  eprint = {2608.09869},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.09869},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs
AU  - G. Arunkumar
AU  - Puja Samanta
PY  - 2026
DA  - 2026/09/13
PB  - arXiv
DO  - 10.48550/arxiv.2608.09869
UR  - https://arxiv.org/abs/2608.09869
AB  - 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≥5, a connected balanced bipartite Parter graph of cycle rank r that has no perfect matching.
ER  -