Dominating bipartite subgraphs in graphs

Gábor Bacsó; Danuta Michalak; Zsolt Tuza

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 1-2, page 85-94
  • ISSN: 2083-5892

Abstract

top
A graph G is hereditarily dominated by a class 𝓓 of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to 𝓓. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.

How to cite

top

Gábor Bacsó, Danuta Michalak, and Zsolt Tuza. "Dominating bipartite subgraphs in graphs." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 85-94. <http://eudml.org/doc/270730>.

@article{GáborBacsó2005,
abstract = {A graph G is hereditarily dominated by a class 𝓓 of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to 𝓓. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.},
author = {Gábor Bacsó, Danuta Michalak, Zsolt Tuza},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {dominating set; dominating subgraph; forbidden induced subgraph; bipartite graph; k-partite graph; -partitie graph},
language = {eng},
number = {1-2},
pages = {85-94},
title = {Dominating bipartite subgraphs in graphs},
url = {http://eudml.org/doc/270730},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Gábor Bacsó
AU - Danuta Michalak
AU - Zsolt Tuza
TI - Dominating bipartite subgraphs in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 1-2
SP - 85
EP - 94
AB - A graph G is hereditarily dominated by a class 𝓓 of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to 𝓓. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.
LA - eng
KW - dominating set; dominating subgraph; forbidden induced subgraph; bipartite graph; k-partite graph; -partitie graph
UR - http://eudml.org/doc/270730
ER -

References

top
  1. [1] G. Bacsó and Zs. Tuza, Dominating cliques in P₅-free graphs, Periodica Math. Hungar. 21 (1990) 303-308, doi: 10.1007/BF02352694. Zbl0746.05065
  2. [2] G. Bacsó and Zs. Tuza, Domination properties and induced subgraphs, Discrete Math. 111 (1993) 37-40, doi: 10.1016/0012-365X(93)90138-J. 
  3. [3] G. Bacsó and Zs. Tuza, Structural domination in graphs, Ars Combin. 63 (2002) 235-256. 
  4. [4] G. Bacsó, Zs. Tuza and M. Voigt, Characterization of graphs dominated by paths of bounded length, to appear. Zbl1114.05069
  5. [5] M.B. Cozzens and L.L. Kelleher, Dominating cliques in graphs, in: Topics on Domination (R. Laskar and S. Hedetniemi, eds.), Discrete Math. 86 (1990) 101-116. Zbl0729.05043
  6. [6] J. Liu and H. Zhou, Dominating subgraphs in graphs with some forbidden structures, Discrete Math. 135 (1994) 163-168, doi: 10.1016/0012-365X(93)E0111-G. Zbl0812.05052
  7. [7] E.S. Wolk, The comparability graph of a tree, Proc. Amer. Math. Soc. 3 (1962) 789-795, doi: 10.1090/S0002-9939-1962-0172273-0. Zbl0109.16402

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.