Tighter Bounds on the Size of a Maximum P 3</sub>-Matching in a Cubic Graph

Adrian Kosowski; Micha? Ma?afiejski; Pawe? ?yliński

首页> 外文期刊>Graphs and Combinatorics >Tighter Bounds on the Size of a Maximum P 3-Matching in a Cubic Graph

【24h】

Tighter Bounds on the Size of a Maximum P 3-Matching in a Cubic Graph

机译：三次图中最大P 3 -匹配的大小的更严格界

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

We establish that for any connected cubic graph G of order n > 16 the maximum P 3-matching in G consists of at least $frac{117}{152}n$ vertices.

机译：我们确定，对于阶数n> 16的任何连通三次方图G，G中的最大P 3 匹配至少包括$ frac {117} {152} n $个顶点。

著录项

来源
《Graphs and Combinatorics》 |2008年第5期|461-468|共8页
作者
Adrian Kosowski; Micha? Ma?afiejski; Pawe? ?yliński;
展开▼
作者单位

Department of Algorithms and System Modelling Gdańsk University of Technology Narutowicza 11/12 80952 Gdańsk Poland;

Department of Algorithms and System Modelling Gdańsk University of Technology Narutowicza 11/12 80952 Gdańsk Poland;

Institute of Computer Science University of Gdańsk Wita Stwosza 57 80952 Gdańsk Poland;

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类
关键词
Path matching; Three-vertex path; Cubic graph;

机译：路径匹配;三顶点路径;三次图;
入库时间 2022-08-18 01:49:06

相似文献

外文文献
中文文献
专利

1. Tighter Bounds on the Size of a Maximum P 3-Matching in a Cubic Graph [J] . Adrian Kosowski, MichaL Malafiejski, Pawel Zyliński Graphs and combinatorics . 2008,第5期

机译：三次图中最大P 3匹配的大小上的紧界
2. Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph [J] . Michael A. Henning, Anders Yeo Graphs and Combinatorics . 2007,第6期

机译：正则图中最大匹配项的大小的紧下界
3. Finding Maximum Induced Matchings in Subclasses of Claw-Free and P_5-Free Graphs, and in Graphs with Matching and Induced Matching of Equal Maximum Size [J] . Daniel Kobler, Udi Rotics Algorithmica . 2003,第4期

机译：在无爪图和无P_5图的子类中以及在具有相等且最大大小相等的匹配和归纳匹配的图中查找最大诱导匹配
4. Tight bounds on the maximum size of a set of permutations with bounded VC-dimension [C] . Josef Cibulka, Jan Kyncl Annual ACM-SIAM Symposium on Discrete Algorithms . 2012

机译：具有界限VC维度的一组排列的最大尺寸的紧张界限
5. Matchings of Intersection Graphs and the Maximum Genus Problem. [D] . El Sherif, Lara. 2016

机译：相交图与最大类问题的匹配。
6. Maximum common subgraph: some upper bound and lower bound results [O] . Xiuzhen Huang, Jing Lai, Steven F Jennings 2006

机译：最大公共子图：一些上限和下限结果
7. Finding Maximum Induced Matchings in Subclasses of Claw-Free and P5-Free Graphs, and in Graphs with Matching and Induced Matching of Equal Maximum Size [O] . Daniel Kobler, Udi Rotics 2003

机译：在无爪和无p5图的子类中以及具有相等最大尺寸的匹配和诱导匹配的图中查找最大诱导匹配

Tighter Bounds on the Size of a Maximum P 3-Matching in a Cubic Graph

摘要

著录项

相似文献

相关主题

期刊订阅