Cover a Tree by Induced Matchings |
Received:June 22, 2008 Revised:June 30, 2009 |
Key Words:
induced matching induced matching cover tree.
|
Fund Project:Supported by the National Natural Science Foundation of China (Grant No.10771179). |
|
Hits: 2318 |
Download times: 1781 |
Abstract: |
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)\}$. |
Citation: |
DOI:10.3770/j.issn:1000-341X.2010.05.010 |
View Full Text View/Add Comment |
|
|
|