pith. sign in

arxiv: 0712.1014 · v1 · submitted 2007-12-06 · 💻 cs.DM

Characterization Of A Class Of Graphs Related To Pairs Of Disjoint Matchings

classification 💻 cs.DM
keywords classgraphgraphsrelationcharacterizationconsiderdisjointmatching
0
0 comments X
read the original abstract

For a given graph consider a pair of disjoint matchings the union of which contains as many edges as possible. Furthermore, consider the relation of the cardinalities of a maximum matching and the largest matching in those pairs. It is known that this relation does not exceed 5/4 for any graph. We characterize the class of graphs for which this relation is precisely 5/4. Our characterization implies that these graphs contain a spanning subgraph, every component of which is the minimal graph of this class.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.