汤京永,董丽,宋新宇.树的导出匹配覆盖[J].数学研究及应用,2010,30(5):845~848
树的导出匹配覆盖
Cover a Tree by Induced Matchings
投稿时间:2008-06-22  最后修改时间:2009-06-30
DOI:10.3770/j.issn:1000-341X.2010.05.010
中文关键词:  导出匹配  导出匹配覆盖  树.
英文关键词:induced matching  induced matching cover  tree.
基金项目:国家自然科学基金(Grant No.10771179).
作者单位
汤京永 信阳师范学院数学与信息科学学院, 河南 信阳 464000 
董丽 信阳师范学院数学与信息科学学院, 河南 信阳 464000 
宋新宇 信阳师范学院数学与信息科学学院, 河南 信阳 464000 
摘要点击次数: 1247
全文下载次数: 1000
中文摘要:
      假设$M_{1},M_{2},\cdots,M_{k}$是$G$的$k$个导出匹配. 我们说$\{M_{1},M_{2},\ldots,M_{k}\}$是$G$的一个$k$ -导出匹配覆盖,如果$V(G)=V(M_{1})\cup \cdots \cup V(M_{k})$. $G$的导出匹配覆盖数 定义为使得$G$有$k$\ -导出匹配覆盖的最小整数$k$,记为$imc(G)$.本文证明了如果$G$是顶点数至少为3的树, 则 $imc(G)\in \{\Delta_{0}^{*}(G),\Delta_{0}^{*}(G) 1,\Delta_{0}^{*}(G) 2\},$ 其中$\Delta_{0}^{*}(G)=\max\{d_{0}(u) d_{0}(v):u,v\in V(G) ,\ uv\in E(G)\}.$
英文摘要:
      The induced matching cover number of a graph $G$ without isolated vertices, denoted by ${\rm imc}(G)$, is the minimum integer $k$ such that $G$ has $k$ induced matchings $M_1, M_2,\ldots,M_k$ such that, $M_1\cup M_2\cup \cdots \cup M_k $ covers $V(G)$. This paper shows if $G$ is a nontrivial tree, then ${\rm imc}(G)\in \{\Delta_{0}^{*}(G),\Delta_{0}^{*}(G) 1,\Delta_{0}^{*}(G) 2\}$, where $\Delta_{0}^{*}(G)=\max\{d_{0}(u) d_{0}(v):u,v\in V(G), uv\in E(G)\}$.
查看全文  查看/发表评论  下载PDF阅读器