کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421166 | 684151 | 2014 | 5 صفحه PDF | دانلود رایگان |
The domination number γ(G)γ(G) and the total domination number γt(G)γt(G) of a graph GG without an isolated vertex are among the most well-studied parameters in graph theory. While the inequality γt(G)≤2γ(G)γt(G)≤2γ(G) is an almost immediate consequence of the definition, the extremal graphs for this inequality are not well understood. Furthermore, even very strong additional assumptions do not allow us to improve the inequality by much.In the present paper we consider the relation of γ(G)γ(G) and γt(G)γt(G) for cubic graphs GG of large girth. Clearly, in this case γ(G)γ(G) is at least n(G)/4n(G)/4 where n(G)n(G) is the order of GG. If γ(G)γ(G) is close to n(G)/4n(G)/4, then this forces a certain structure within GG. We exploit this structure and prove an upper bound on γt(G)γt(G), which depends on the value of γ(G)γ(G). As a consequence, we can considerably improve the inequality γt(G)≤2γ(G)γt(G)≤2γ(G) for cubic graphs of large girth.
Journal: Discrete Applied Mathematics - Volume 174, 10 September 2014, Pages 128–132