Total outer-connected domination in trees

Joanna Cyman

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 3, page 377-383
  • ISSN: 2083-5892

Abstract

top
Let G = (V,E) be a graph. Set D ⊆ V(G) is a total outer-connected dominating set of G if D is a total dominating set in G and G[V(G)-D] is connected. The total outer-connected domination number of G, denoted by γ t c ( G ) , is the smallest cardinality of a total outer-connected dominating set of G. We show that if T is a tree of order n, then γ t c ( T ) ≥ ⎡ 2 n / 3 ⎤ . Moreover, we constructively characterize the family of extremal trees T of order n achieving this lower bound.

How to cite

top

Joanna Cyman. "Total outer-connected domination in trees." Discussiones Mathematicae Graph Theory 30.3 (2010): 377-383. <http://eudml.org/doc/270887>.

@article{JoannaCyman2010,
abstract = {Let G = (V,E) be a graph. Set D ⊆ V(G) is a total outer-connected dominating set of G if D is a total dominating set in G and G[V(G)-D] is connected. The total outer-connected domination number of G, denoted by $γ_\{tc\}(G)$, is the smallest cardinality of a total outer-connected dominating set of G. We show that if T is a tree of order n, then $γ_\{tc\}(T) ≥ ⎡2n/3⎤$. Moreover, we constructively characterize the family of extremal trees T of order n achieving this lower bound.},
author = {Joanna Cyman},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {total outer-connected domination number; domination number},
language = {eng},
number = {3},
pages = {377-383},
title = {Total outer-connected domination in trees},
url = {http://eudml.org/doc/270887},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Joanna Cyman
TI - Total outer-connected domination in trees
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 3
SP - 377
EP - 383
AB - Let G = (V,E) be a graph. Set D ⊆ V(G) is a total outer-connected dominating set of G if D is a total dominating set in G and G[V(G)-D] is connected. The total outer-connected domination number of G, denoted by $γ_{tc}(G)$, is the smallest cardinality of a total outer-connected dominating set of G. We show that if T is a tree of order n, then $γ_{tc}(T) ≥ ⎡2n/3⎤$. Moreover, we constructively characterize the family of extremal trees T of order n achieving this lower bound.
LA - eng
KW - total outer-connected domination number; domination number
UR - http://eudml.org/doc/270887
ER -

References

top
  1. [1] G. Chartrand and L. Leśniak, Graphs & Digraphs (Wadsworth and Brooks/Cole, Monterey, CA, third edition, 1996). 
  2. [2] E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304. Zbl0447.05039
  3. [3] G.S. Domke, J.H. Hattingh, M.A. Henning and L.R. Markus, Restrained domination in trees, Discrete Math. 211 (2000) 1-9, doi: 10.1016/S0012-365X(99)00036-9. Zbl0947.05057
  4. [4] J.H. Hattingh, E. Jonck, E.J. Joubert and A.R. Plummer, Total Restrained Domination in Trees, Discrete Math. 307 (2007) 1643-1650, doi: 10.1016/j.disc.2006.09.014. Zbl1132.05044
  5. [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  6. [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). Zbl0883.00011

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.