Cover the Vertices of a Tree by Matchings
NG Hong-wei · Journal of Zhengzhou University · 2006
The matching cover number of a graphGwithout isolated vertices,denoted bymc(G),is the mini mumin-tegerksuch thatGhaskmatchingsM1,M2,…,MkthatM1∪M2∪…∪MkcoverV(G).It is shown that ifGis atree,thenmc(G)∈{Δ0(G),Δ0(G)+1},whereΔ0(G)is the maxi mumnumberlsuchthat a certain vertex ofGis ad-jacent tolvertices of degree 1.Moreover,given a treeG,the matching cover number ofGcan be determined by a lin-ear-ti me algorithm.