کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646734 | 1342311 | 2017 | 10 صفحه PDF | دانلود رایگان |
We show that if GG is a graph with minimum degree at least three, then γt(G)≤α′(G)+(pc(G)−1)∕2γt(G)≤α′(G)+(pc(G)−1)∕2 and this bound is tight, where γt(G)γt(G) is the total domination number of GG, α′(G)α′(G) the matching number of GG and pc(G)pc(G) the path covering number of GG which is the minimum number of vertex disjoint paths such that every vertex belongs to a path in the cover. We show that if GG is a connected graph on at least six vertices, then γnt(G)≤α′(G)+pc(G)∕2γnt(G)≤α′(G)+pc(G)∕2 and this bound is tight, where γnt(G)γnt(G) denotes the neighborhood total domination number of GG. We observe that every graph GG of order nn satisfies α′(G)+pc(G)∕2≥n∕2α′(G)+pc(G)∕2≥n∕2, and we characterize the trees achieving equality in this bound.
Journal: Discrete Mathematics - Volume 340, Issue 1, 6 January 2017, Pages 3207–3216