Graph domination in distance two

Gábor Bacsó; Attila Tálos; Zsolt Tuza

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 1-2, page 121-128
  • ISSN: 2083-5892

Abstract

top
Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class of graphs, Domₖ is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ which is also connected. In our notation, Dom coincides with Dom₁. In this paper we prove that D o m D o m u = D o m ₂ u holds for u = all connected graphs without induced P u (u ≥ 2). (In particular, ₂ = K₁ and ₃ = all complete graphs.) Some negative examples are also given.

How to cite

top

Gábor Bacsó, Attila Tálos, and Zsolt Tuza. "Graph domination in distance two." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 121-128. <http://eudml.org/doc/270765>.

@article{GáborBacsó2005,
abstract = {Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class of graphs, Domₖ is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ which is also connected. In our notation, Dom coincides with Dom₁. In this paper we prove that $Dom Dom _u = Dom₂ _u$ holds for $_u$ = all connected graphs without induced $P_u$ (u ≥ 2). (In particular, ₂ = K₁ and ₃ = all complete graphs.) Some negative examples are also given.},
author = {Gábor Bacsó, Attila Tálos, Zsolt Tuza},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph; dominating set; connected domination; distance domination; forbidden induced subgraph; -dominating subgraph},
language = {eng},
number = {1-2},
pages = {121-128},
title = {Graph domination in distance two},
url = {http://eudml.org/doc/270765},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Gábor Bacsó
AU - Attila Tálos
AU - Zsolt Tuza
TI - Graph domination in distance two
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 1-2
SP - 121
EP - 128
AB - Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class of graphs, Domₖ is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ which is also connected. In our notation, Dom coincides with Dom₁. In this paper we prove that $Dom Dom _u = Dom₂ _u$ holds for $_u$ = all connected graphs without induced $P_u$ (u ≥ 2). (In particular, ₂ = K₁ and ₃ = all complete graphs.) Some negative examples are also given.
LA - eng
KW - graph; dominating set; connected domination; distance domination; forbidden induced subgraph; -dominating subgraph
UR - http://eudml.org/doc/270765
ER -

References

top
  1. [1] G. Bacsó and Zs. Tuza, A characterization of graphs without long induced paths, J. Graph Theory 14 (1990) 455-464, doi: 10.1002/jgt.3190140409. 
  2. [2] G. Bacsó and Zs. Tuza, Dominating cliques in P₅-free graphs, Periodica Math. Hungar. 21 (1990) 303-308, doi: 10.1007/BF02352694. 
  3. [3] G. Bacsó and Zs. Tuza, Domination properties and induced subgraphs, Discrete Math. 1 (1993) 37-40. 
  4. [4] G. Bacsó and Zs. Tuza, Dominating subgraphs of small diameter, J. Combin. Inf. Syst. Sci. 22 (1997) 51-62. 
  5. [5] G. Bacsó and Zs. Tuza, Structural domination in graphs, Ars Combinatoria 63 (2002) 235-256. 
  6. [6] M.B. Cozzens and L.L. Kelleher, Dominating cliques in graphs, pp. 101-116 in [10]. Zbl0729.05043
  7. [7] P. Erdős, M. Saks and V.T. Sós Maximum induced trees in graphs, J. Combin. Theory (B) 41 (1986) 61-79, doi: 10.1016/0095-8956(86)90028-6. Zbl0603.05023
  8. [8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, N.Y., 1998). Zbl0890.05002
  9. [9] E.S. Wolk, The comparability graph of a tree, Proc. Amer. Nath. Soc. 3 (1962) 789-795, doi: 10.1090/S0002-9939-1962-0172273-0. Zbl0109.16402
  10. [10] - Topics on Domination (R. Laskar and S. Hedetniemi, eds.), Annals of Discrete Math. 86 (1990). 

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.