PDF

Discussiones Mathematicae Graph Theory 28(1) (2008) 109-119
DOI: https://doi.org/10.7151/dmgt.1395

WEAKLY CONNECTED DOMINATION SUBDIVISION NUMBERS

Joanna Raczek

Department of Discrete Mathematics
Faculty of Applied Physics and Mathematics
Gdańsk University of Technology
Narutowicza 11/12, 80-952 Gdańsk, Poland
e-mail: gardenia@pg.gda.pl

Abstract

A set D of vertices in a graph G = (V,E) is a weakly connected dominating set of G if D is dominating in G and the subgraph weakly induced by D is connected. The weakly connected domination number of G is the minimum cardinality of a weakly connected dominating set of G. The weakly connected domination subdivision number of a connected graph G is the minimum number of edges that must be subdivided (where each egde can be subdivided at most once) in order to increase the weakly connected domination number. We study the weakly connected domination subdivision numbers of some families of graphs.

Keywords: weakly connected domination number, weakly connected domination subdivision number.

2000 Mathematics Subject Classification: 05C69.

References

[1]	G.S. Domke, J.H. Hattingh and L.R. Marcus, On weakly connected domination in graphs II, Discrete Math. 305 (2005) 112-122, doi: 10.1016/j.disc.2005.10.006.
[2]	J.E. Dunbar, J.W. Grossman, J.H. Hattingh, S.T. Hedetniemi and A.A. McRae, On weakly connected domination in graphs, Discrete Math. 167/168 (1997) 261-269, doi: 10.1016/S0012-365X(96)00233-6.
[3]	T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998).
[4]	T.W. Haynes, M.A. Henning and L.S. Hopkins, Total domination subdivision numbers of graphs, Discuss. Math. Graph Theory 24 (2003) 457-467, doi: 10.7151/dmgt.1244.
[5]	J.H. Hattingh, E. Jonck and L.R. Marcus, A note on the weakly connected subdivision number of a graph (2007), to appear.

Received 10 November 2006
Revised 18 December 2007
Accepted 18 December 2007