For a given connected graph G = (V, E), a set is a doubly connected dominating set if it is dominating and both 〈D〉 and 〈V (G)-D〉 are connected. The cardinality of the minimum doubly connected dominating set in G is the doubly connected domination number. We investigate several properties of doubly connected dominating sets and give some bounds on the doubly connected domination number.
@article{bwmeta1.element.doi-10_1007_s11533-005-0003-4,
author = {Joanna Cyman and Magdalena Lema\'nska and Joanna Raczek},
title = {On the doubly connected domination number of a graph},
journal = {Open Mathematics},
volume = {4},
year = {2006},
pages = {34-45},
zbl = {1101.05047},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_1007_s11533-005-0003-4}
}
Joanna Cyman; Magdalena Lemańska; Joanna Raczek. On the doubly connected domination number of a graph. Open Mathematics, Tome 4 (2006) pp. 34-45. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_1007_s11533-005-0003-4/
[1] J.A. Bondy and U.S.R. Murty: Graph Theory with Applications, Macmillan, London, 1976.
[2] C. Bo and B. Liu: “Some inequalities about connected domination number”, Disc. Math., Vol. 159, (1996), pp. 241–245. http://dx.doi.org/10.1016/0012-365X(95)00088-E
[3] P. Duchet and H. Meyniel: “On Hadwiger's number and the stability number”, Ann. Disc. Math., Vol. 13, (1982), pp. 71–74. | Zbl 0522.05060
[4] M.R. Garey and D.S. Johnson: Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979. | Zbl 0411.68039
[5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater: Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998. | Zbl 0890.05002
[6] S.T. Hedetniemi and R. Laskar: Connected domination in graphs, Graph Theory and Combinatorics, Academic Press, London, 1984, pp. 209–217.
[7] E. Sampathkumar and H.B. Walikar: “The connected domination number of a graph”, J. Math. Phys. Sci., Vol. 13, (1979), pp. 607–613. | Zbl 0449.05057