Cover a Tree by Induced Matchings

DOI：10.3770/j.issn:1000-341X.2010.05.010

 作者 单位 汤京永 信阳师范学院数学与信息科学学院, 河南 信阳 464000 董丽 信阳师范学院数学与信息科学学院, 河南 信阳 464000 宋新宇 信阳师范学院数学与信息科学学院, 河南 信阳 464000

假设$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)\}$.