On the doubly connected domination number of a graph

• Autorzy: Joanna Cyman , Magdalena Lemańska , Joanna Raczek
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Doubly connected domination number; connected domination number; 05C69

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2006
• Tom: 4
• Numer: 1
• Strony: 34-45

Daty

wydano

2006-03-01

online

2006-03-01

Twórcy

autor

Joanna Cyman

• Gdańsk University of Technology

autor

Magdalena Lemańska

• Gdańsk University of Technology

autor

Joanna Raczek

• Gdańsk University of Technology

Bibliografia

• [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.
• [4] M.R. Garey and D.S. Johnson: Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979.
• [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater: Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
• [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.

Identyfikatory

DOI

10.1007/s11533-005-0003-4