Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 33 min ago
PreprintarXiv licencearXiv

The maximum size of simple solid matching covered graphs

  • Tong Zhang
  • Wei Li
Open at sourcePDFDOICite

Abstract

A connected graph with at least two vertices is matching covered if each of its edges is contained in a perfect matching. A matching covered graph is solid if every separating cut in it is a tight cut. A matching covered graph which is free of nontrivial tight cuts is a brick if it is nonbipartite. Every bipartite matching covered graph is solid. Lucchesi and Murty conjectured that there exists a positive integer N such that, for every integer n≥ N, the maximum number of edges in a simple solid matching covered graph on 2n vertices is n2. In this paper, we disprove this Conjecture, and show that the maximum number of edges of a simple solid matching covered graph on 2n (n≥2) vertices is n2+2. Moreover, we characterize the graphs attaining this bound. In addition, we prove that every simple solid brick of order 2n has at most n2 edges for n≥4.

Related

  1. The maximum number of edges in minimal matching covered graphs
    Xiaoling He
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Central Limit Theorem of Maximum Weight Matching on Random Graphs with Prescribed Degrees
    Shichen Jing, Wai-Kit Lam, Arnab Sen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  3. On graphs whose powers are well-covered
    My Hanh Pham, Thanh Vu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Well-Covered Powers: Cartesian Products and Cayley Graphs
    Haobo Ma, Thanh Vu, Wenlin Zhang
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Maximum spread of vertex degrees in a simple graph
    Sergey Onishchenko
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{zhang2026maximum,
  title = {{The maximum size of simple solid matching covered graphs}},
  author = {Tong Zhang and Wei Li},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.07733},
  eprint = {2610.07733},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.07733},
}
RIS
TY  - UNPB
TI  - The maximum size of simple solid matching covered graphs
AU  - Tong Zhang
AU  - Wei Li
PY  - 2026
DA  - 2026/10/06
PB  - arXiv
DO  - 10.48550/arxiv.2610.07733
UR  - https://arxiv.org/abs/2610.07733
AB  - A connected graph with at least two vertices is matching covered if each of its edges is contained in a perfect matching. A matching covered graph is solid if every separating cut in it is a tight cut. A matching covered graph which is free of nontrivial tight cuts is a brick if it is nonbipartite. Every bipartite matching covered graph is solid. Lucchesi and Murty conjectured that there exists a positive integer N such that, for every integer n≥ N, the maximum number of edges in a simple solid matching covered graph on 2n vertices is n^2. In this paper, we disprove this Conjecture, and show that the maximum number of edges of a simple solid matching covered graph on 2n (n≥2) vertices is n^2+2. Moreover, we characterize the graphs attaining this bound. In addition, we prove that every simple solid brick of order 2n has at most n^2 edges for n≥4.
ER  -