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).
Author NameAffiliation
Jing Yong TANG College of Mathematics and Information Science, Xinyang Normal University, Henan 464000, P. R. China 
Li DONG College of Mathematics and Information Science, Xinyang Normal University, Henan 464000, P. R. China 
Xin Yu SONG College of Mathematics and Information Science, Xinyang Normal University, Henan 464000, P. R. China 
Hits: 2310
Download times: 1776
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