树的导出匹配覆盖

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_1cup M_2cup 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,vin V(G), uvin E(G)}$.