Matchings, path covers and domination

作者：Henning Michael A; Wash Kirsti^*

来源：Discrete Mathematics, 2017, 340(1): 3207-3216.

DOI：10.1016/j.disc.2016.07.020

• Matching
• Path cover
• Total domination
• Neighborhood total domination

We show that if G is a graph with minimum degree at least three, then gamma(t)(G) <= alpha'(G) + (pc(G)-1)/2 and this bound is tight, where gamma(t)(G) is the total domination number of G, alpha'(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 gamma(nt)(G) <= alpha'(G) + pc(G)/2 and this bound is tight, where gamma(nt)(G) denotes the neighborhood total domination number of G. We observe that every graph G of order n satisfies alpha'(G) + pc(G)/2 >= n/2, and we characterize the trees achieving equality in this bound.

• 出版日期2017-1-6