PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2005 | 25 | 3 | 291-302
Tytuł artykułu

Exact double domination in graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
In a graph a vertex is said to dominate itself and all its neighbours. A doubly dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. A doubly dominating set is exact if every vertex of G is dominated exactly twice. We prove that the existence of an exact doubly dominating set is an NP-complete problem. We show that if an exact double dominating set exists then all such sets have the same size, and we establish bounds on this size. We give a constructive characterization of those trees that admit a doubly dominating set, and we establish a necessary and sufficient condition for the existence of an exact doubly dominating set in a connected cubic graph.
Słowa kluczowe
Wydawca
Rocznik
Tom
25
Numer
3
Strony
291-302
Opis fizyczny
Daty
wydano
2005
otrzymano
2004-01-15
poprawiono
2004-11-08
Twórcy
  • Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
  • Department of Operations Research, Faculty of Mathematics, University of Sciences and Technology Houari Boumediene, B.P. 32, El Alia, Bab Ezzouar, Algiers, Algeria
  • C.N.R.S., Laboratoire Leibniz-IMAG, 46 Avenue Félix Viallet, 38031 Grenoble Cedex, France
Bibliografia
  • [1] D.W. Bange, A.E. Barkauskas and P.J. Slater, Efficient dominating sets in graphs, in: Applications of Discrete Mathematics, R.D. Ringeisen and F.S. Roberts, eds (SIAM, Philadelphia, 1988) 189-199.
  • [2] M. Blidia, M. Chellali and T.W. Haynes, Characterizations of trees with equal paired and double domination numbers, submitted for publication.
  • [3] M. Blidia, M. Chellali, T.W. Haynes and M. Henning, Independent and double domination in trees, to appear in Utilitas Mathematica.
  • [4] M. Chellali and T.W. Haynes, On paired and double domination in graphs, to appear in Utilitas Mathematica.
  • [5] M. Farber, Domination, independent domination and duality in strongly chordal graphs, Discrete Appl. Math. 7 (1984) 115-130, doi: 10.1016/0166-218X(84)90061-1.
  • [6] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness (W.H. Freeman, San Francisco, 1979).
  • [7] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201-213.
  • [8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
  • [9] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1282
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.