树的匹配覆盖

• 作者: 宋晓新 梁宏伟
• 来源期刊: 郑州大学学报（理学版）
• 学科: 数学
• 关键词: 匹配 匹配覆盖 悬挂度
• 年，卷（期）: 2006,（1）
• 页码范围: 24-27,40
• 页数: 5页
• 分类号: O1
• 语种: 中文
• DOI: 10.3969/j.issn.1671-6841.2006.01.005

摘要

设图G没有孤立点.图G的匹配覆盖数,记为mc(G),是指满足如下条件的最小正整数k:G有k个匹配M1,M2,…,Mk覆盖图G的所有顶点.证明了如果图G是一个树,则mc(G)∈{△0(G),△0(G)+1},其中△0(G)是指使得图G的某个顶点有l个一度邻点的l的最大值.而且,任给一个树G,给出了一个可以确定图G的匹配覆盖数的线性算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宋晓新	河南大学数学与信息科学学院	18	14	2.0	2.0
5	梁宏伟	河南大学数学与信息科学学院	15	34	3.0	5.0