| 汤京永,董丽,宋新宇.树的导出匹配覆盖[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). |
|
| 摘要点击次数: 2315 |
| 全文下载次数: 1779 |
| 中文摘要: |
| 假设$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阅读器 |
|
|
|
