...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
【24h】

Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids

机译：具有最大限制唯一匹配的无三角形图及其对应的贪婪

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A matching M is uniquely restricted in a graph G if its saturated vertices induce a subgraph which has a unique perfect matching, namely M itself [M.C. Golumbic, T. Hirst, M. Lewenstein, Uniquely restricted matchings, Algorithmica 31 (2001) 139-154]. G is a Konig-Egervary graph provided alpha(G) + mu(G) = vertical bar V(G)vertical bar [R.W. Deming, Independence numbers of graphs-an extension of the Konig-Egervary theorem, Discrete Math. 27 (1979) 23-33; F. Sterboul, A characterization of the graphs in which the transversal number equals the matching number, J. Combin. Theory Ser. B 27 (1979) 228-229], where mu(G) is the size of a maximum matching and alpha(G) is the cardinality of a maximum stable set. S is a local maximum stable set of G, and we write S epsilon Psi(G), if S is a maximum stable set of the subgraph spanned by S boolean OR N(S), where N(S) is the neighborhood of S. Nernhauser and Trotter [Vertex packings: structural properties and algorithms, Math. Programming 8 (1975) 232-248], proved that any S epsilon Psi(G) is a subset of a maximum stable set of G. In [V.E. Levit, E. Mandrescu, Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings, Discrete Appl. Math. 132 (2003) 163-174] we have proved that for a bipartite graph G, Psi(G) is a greedoid on its vertex set if and only if all its maximum matchings are uniquely restricted. In this paper we demonstrate that if G is a triangle-free graph, then Psi(G) is a greedoid if and only if all its maximum matchings are uniquely restricted and for any S epsilon psi(G), the subgraph spanned by S boolean OR N(S) is a Konig-Egervary graph. (c) 2007 Elsevier B.V. All rights reserved.
机译：如果匹配M的饱和顶点诱导出具有唯一完美匹配的子图，即M本身，则匹配M在图G中被唯一地限制。 Golumbic，T。Hirst，M。Lewenstein，唯一受限匹配，Algorithica 31（2001）139-154]。 G是Konig-Egervary图，它提供alpha（G）+ mu（G）=竖线V（G）竖线[R.W. Deming，图的独立数-Konig-Egervary定理“离散数学”的扩展。 27（1979）23-33; F. Sterboul，图的特征，其中横数等于匹配数，J。Combin。理论系列B 27（1979）228-229]，其中mu（G）是最大匹配的大小，而alpha（G）是最大稳定集的基数。 S是G的局部最大稳定集，如果S是由S布尔OR N（S）跨越的子图的最大稳定集，则我们写出S epsilon Psi（G），其中N（S）是S的邻域Nernhauser和Trotter [顶点填充：结构特性和算法，数学程序8（1975）232-248]证明，任何SεPsi（G）都是G的最大稳定集的子集。 Levit，E。Mandrescu，二分图中具有唯一限制的最大匹配的局部最大稳定集，离散应用。数学。 132（2003）163-174]我们证明，对于二部图G，当且仅当其所有最大匹配都受到唯一限制时，Psi（G）才是其顶点集上的贪婪。在本文中，我们证明，如果G是无三角形的图，则Psi（G）是greeedoid且仅当其所有最大匹配都受到唯一限制且对于任何S epsilon psi（G）时，子图都由S布尔值覆盖OR N（S）是Konig-Egervary图。 （c）2007 Elsevier B.V.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号