Restrained domination in cubic graphs
Tóm tắt
Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γ
r
(G), is the smallest cardinality of a restrained dominating set of G. A graph G is said to be cubic if every vertex has degree three. In this paper, we study restrained domination in cubic graphs. We show that if G is a cubic graph of order n, then
$\gamma_{r}(G)\geq \frac{n}{4}$
, and characterize the extremal graphs achieving this lower bound. Furthermore, we show that if G is a cubic graph of order n, then
$\gamma _{r}(G)\leq \frac{5n}{11}.$
Lastly, we show that if G is a claw-free cubic graph, then γ
r
(G)=γ(G).
Tài liệu tham khảo
Chen XG, Ma DX, Sun L (2005) On total restrained domination in graphs. Czechoslov Math J 55(1): 165–173
Dankelmann P, Hattingh JH, Henning MA, Swart HC (2006) Trees with equal domination and restrained domination numbers. J Glob Optim 34:597–607
Dankelmann P, Day D, H Hattingh J, Henning MA, Markus LR, Swart HC (2007) On equality in an upper bound for the restrained and total domination numbers of a graph. Discrete Math 307:2845–2852
Domke GS, Hattingh JH, Hedetniemi ST, Laskar RC, Markus LR (1999) Restrained domination in graphs. Discrete Math 203:61–69
Domke GS, Hattingh JH, Hedetniemi ST, Markus LR (2000a) Restrained domination in trees. Discrete Math 211:1–9
Domke GS, Hattingh JH, Henning MA, Markus LR (2000b) Restrained domination in graphs with minimum degree two. J Comb Math Comb Comput 35:239–254
Hattingh JH, Henning MA (2008) Restrained domination excellent trees. Ars Comb 87:337–351
Hattingh JH, Plummer AR (2009) A note on restrained domination in trees. Ars Comb (to appear)
Hattingh JH, Jonck E, Joubert EJ, Plummer AR (2008) Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs. Discrete Math 308:1080–1087
Haynes TW, Hedetniemi ST, Slater PJ (1997a) Fundamentals of domination in graphs. Dekker, New York
Haynes TW, Hedetniemi ST, Slater PJ (eds) (1997b) Domination in graphs: advanced topics. Dekker, New York
Henning MA (1999) Graphs with large restrained domination number. Discrete Math 197/198:415–429
Jiang HX, Kang LY, Shan EF (2009) Total restrained domination in cubic graphs. Graphs Comb 25: 341–350
Telle JA, Proskurowski A (1997) Algorithms for vertex partitioning problems on partial k-trees. SIAM J Discrete Math 10:529–550
Zelinka B (2005) Remarks on restrained and total restrained domination in graphs. Czechoslov Math J 55(130):165–173