文摘
We show that if G is a graph with minimum degree at least three, then γt(G)≤α′(G)+(pc(G)−1)∕2 and this bound is tight, where γt(G) is the total domination number of G, α′(G) the matching number of G and pc(G) the path covering number of G which is the minimum number of vertex disjoint paths such that every vertex belongs to a path in the cover. We show that if G is a connected graph on at least six vertices, then γnt(G)≤α′(G)+pc(G)∕2 and this bound is tight, where γnt(G) denotes the neighborhood total domination number of G. We observe that every graph G of order n satisfies α′(G)+pc(G)∕2≥n∕2, and we characterize the trees achieving equality in this bound.