Abstract
For a given connected graph G = (V, E), a set \(D \subseteq V(G)\) 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 PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J.A. Bondy and U.S.R. Murty: Graph Theory with Applications, Macmillan, London, 1976.
C. Bo and B. Liu: “Some inequalities about connected domination number”, Disc. Math., Vol. 159, (1996), pp. 241–245.
P. Duchet and H. Meyniel: “On Hadwiger's number and the stability number”, Ann. Disc. Math., Vol. 13, (1982), pp. 71–74.
M.R. Garey and D.S. Johnson: Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979.
T.W. Haynes, S.T. Hedetniemi and P.J. Slater: Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
S.T. Hedetniemi and R. Laskar: Connected domination in graphs, Graph Theory and Combinatorics, Academic Press, London, 1984, pp. 209–217.
E. Sampathkumar and H.B. Walikar: “The connected domination number of a graph”, J. Math. Phys. Sci., Vol. 13, (1979), pp. 607–613.
Author information
Authors and Affiliations
About this article
Cite this article
Cyman, J., Lemańska, M. & Raczek, J. On the doubly connected domination number of a graph. centr.eur.j.math. 4, 34–45 (2006). https://doi.org/10.1007/s11533-005-0003-4
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s11533-005-0003-4