The maximum size of simple solid matching covered graphs
En palabras de los autores
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 .
Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.