吴龙树,闫运生,王勤.3阶幂图的广义导出匹配可扩性[J].数学研究及应用,2010,30(3):451~456
3阶幂图的广义导出匹配可扩性
General Induced Matching Extendability of $G^3$
投稿时间:2008-12-01  最后修改时间:2009-09-18
DOI:10.3770/j.issn:1000-341X.2010.03.009
中文关键词:  几乎完美匹配  导出匹配可扩的  广义导出匹配可扩性  幂图.
英文关键词:near perfect matching  induced matching extendable  general induced matching extendability  power of graph.
基金项目:国家自然科学基金(Grant Nos.10601051; 90818020); 浙江省自然科学基金(Grant No.Y6090472).
作者单位
吴龙树 中国计量学院数学系, 浙江 杭州 310018 
闫运生 河南工业大学理学院, 河南 郑州 450052 
王勤 中国计量学院数学系, 浙江 杭州 310018 
摘要点击次数: 1593
全文下载次数: 865
中文摘要:
      图$G$称为是导出匹配可扩的,如果图$G$的每一个导出匹配都包含在它的一个完美匹配中.图$G$称为是广义导出匹配可扩的,如果图$G$的每一个导出匹配都包含在它的一个最大基数匹配中.图$G$称为是无爪的,如果它不包含任何与$K_{1,3}$同构的导出子图.图$G$的$k$阶幂图记为$G^k$,是指在它的顶点集$V(G)$中,两个顶点相邻当且仅当它们在图$G$中的距离至多为$k$.在本文中我们证明了,如果图$G$的最大匹配和$G^3$的最大匹配的基数相同,那么$G^3$是广义导出匹配可扩的.我们证明了这个结果是最佳可能的.同时,我们证明了如果$G$是连通的无爪图,那么$G^3$是广义导出匹配可扩的.
英文摘要:
      A graph $G$ is induced matching extendable if every induced matching of $G$ is included in a perfect matching of $G$. A graph $G$ is generalized induced matching extendable if every induced matching of $G$ is included in a maximum matching of $G$. A graph $G$ is claw-free, if $G$ dose not contain any induced subgraph isomorphic to $K_{1,3}$. The $k$-th power of $G$, denoted by $G^k$, is the graph with vertex set $V(G)$ in which two vertices are adjacent if and only if the distance between them is at most $k$ in $G$. In this paper we show that, if the maximum matchings of $G$ and $G^3$ have the same cardinality, then $G^3$ is generalized induced matching extendable. We also show that this result is best possible. As a result, we show that if $G$ is a connected claw-free graph, then $G^3$ is generalized induced matching extendable.
查看全文  查看/发表评论  下载PDF阅读器