Dominating bipartite subgraphs in graphs

• Autorzy: Gábor Bacsó , Danuta Michalak , Zsolt Tuza
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

dominating set; dominating subgraph; forbidden induced subgraph; bipartite graph; k-partite graph

Kategorie tematyczne

• 05C75: Structural characterization of families of graphs
• 05C38: Paths and cycles
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2005
• Tom: 25
• Numer: 1-2
• Strony: 85-94

Daty

wydano

2005

otrzymano

2003-10-31

poprawiono

2004-06-16

Twórcy

autor

Gábor Bacsó

• Computer and Automation Institute, Hungarian Academy of Sciences, H-1111 Budapest, Kende u. 13-17, Hungary

autor

Danuta Michalak

• Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Podgórna 50, 65-246 Zielona Góra, Poland

autor

Zsolt Tuza

• Computer and Automation Institute, Hungarian Academy of Sciences
• Department of Computer Science, University of Veszprém

Bibliografia

• [1] G. Bacsó and Zs. Tuza, Dominating cliques in P₅-free graphs, Periodica Math. Hungar. 21 (1990) 303-308, doi: 10.1007/BF02352694.
• [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] G. Bacsó and Zs. Tuza, Structural domination in graphs, Ars Combin. 63 (2002) 235-256.
• [4] G. Bacsó, Zs. Tuza and M. Voigt, Characterization of graphs dominated by paths of bounded length, to appear.
• [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.
• [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.
• [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.

Identyfikatory

DOI

10.7151/dmgt.1263