PDF
Discussiones Mathematicae Graph Theory 25(1-2) (2005)
85-94
DOI: https://doi.org/10.7151/dmgt.1263
DOMINATING BIPARTITE SUBGRAPHS IN GRAPHS
|
Gábor Bacsó
Computer and Automation Institute |
Danuta Michalak
Faculty of Mathematics Computer Science and Econometrics University of Zielona Góra Podgórna 50, 65-246 Zielona Góra, Poland e-mail: d.michalak@wmie.uz.zgora.pl |
Zsolt Tuza
Computer and Automation Institute |
Abstract
A graph G is hereditarily dominated by a class D of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to D. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.Keywords: dominating set, dominating subgraph, forbidden induced subgraph, bipartite graph, k-partite graph.
2000 Mathematics Subject Classification: 05C69, 05C38, 05C75.
References
| [1] | G. Bacsó and Zs. Tuza, Dominating cliques in P5-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. |
Received 31 October 2003
Revised 16 June 2004
Close