Characterization of a class of graphs related to pairs of disjoint matchings
Characterization of a class of graphs related to pairs of disjoint matchings
复制标题
与不相交匹配对相关的一类图的表征
DOI：
10.1016/j.disc.2008.01.004
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
A. Tserunyan
中科院分区：
文献类型：
--
作者：
A. Tserunyan
对于一个给定的图，考虑一对不相交的匹配，其并集包含尽可能多的边。此外，考虑最大匹配和这些对中最大匹配的基数之比。已知对于任何图，54是该比率的严格上限。我们刻画的类图，它正好是54。我们的刻画意味着这些图包含一个生成子图，它的每一个连通分支都是这类图的最小图。
For a given graph consider a pair of disjoint matchings the union of which contains as many edges as possible. Furthermore, consider the ratio of the cardinalities of a maximum matching and the largest matching in those pairs. It is known that for any graph 54 is the tight upper bound for this ratio. We characterize the class of graphs for which it is precisely 54. Our characterization implies that these graphs contain a spanning subgraph, every connected component of which is the minimal graph of this class.