Generalized subgraph-restricted matchings in graphs
Generalized subgraph-restricted matchings in graphs
复制标题
DOI：
10.1016/j.disc.2004.08.027
复制
发表时间：
2005-04-06
影响因子：
0.8
通讯作者：
Laskar, R
中科院分区：
文献类型：
--
作者：
Goddard, W;Hedetniemi, SM;Laskar, R
对于一个图的属性P，我们定义一个P-匹配作为一组M的不相交的边缘，使子图所引起的事件到M的顶点具有属性P。以前的例子包括强/诱导匹配和唯一限制匹配。我们探讨了P-匹配的一般性质，特别是P是非循环的性质或不连通的性质的情况。我们考虑的界限和复杂性的最大基数的P-匹配和最小基数的最大P-匹配。(c)2005 Elsevier B. V.保留所有权利。
For a graph property P, we define a P-matching as a set M of disjoint edges such that the subgraph induced by the vertices incident to M has property P. Previous examples include strong/induced matchings and uniquely restricted matchings. We explore the general properties of P-matchings, but especially the cases where P is the property of being acyclic or the property of being disconnected. We consider bounds on and the complexity of the maximum cardinality of a P-matching and the minimum cardinality of a maximal P-matching. (c) 2005 Elsevier B.V. All rights reserved.