pipette
ESEspañol

The maximum size of simple solid matching covered graphs

Tong Zhang, Wei Li

Preprint

In the authors' words

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 such that, for every integer , the maximum number of edges in a simple solid matching covered graph on vertices is . In this paper, we disprove this Conjecture, and show that the maximum number of edges of a simple solid matching covered graph on () vertices is . Moreover, we characterize the graphs attaining this bound. In addition, we prove that every simple solid brick of order has at most edges for .

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.