树的导出匹配覆盖

The induced matching cover number of a graph G without isolated vertices,denoted by imc(G),is the minimum integer k such that G has k induced matchings M1,M2,…,Mk such that,M1∪M2 ∪…∪Mk covers V(G).This paper shows if G is a nontrivial tree,then imc(G) ∈ {△*0(G),△*0(G) + 1,△*0(G)+2},where △*0(G) = max{d0(u) + d0(v) :u,v ∈ V(G),uv ∈ E(G)}.

Cover a Tree by Induced Matchings

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