PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2012 | 32 | 2 | 263-270
Tytuł artykułu

Trees with equal 2-domination and 2-independence numbers

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Let G = (V,E) be a graph. A subset S of V is a 2-dominating set if every vertex of V-S is dominated at least 2 times, and S is a 2-independent set of G if every vertex of S has at most one neighbor in S. The minimum cardinality of a 2-dominating set a of G is the 2-domination number γ₂(G) and the maximum cardinality of a 2-independent set of G is the 2-independence number β₂(G). Fink and Jacobson proved that γ₂(G) ≤ β₂(G) for every graph G. In this paper we provide a constructive characterization of trees with equal 2-domination and 2-independence numbers.
Słowa kluczowe
Wydawca
Rocznik
Tom
32
Numer
2
Strony
263-270
Opis fizyczny
Daty
wydano
2012
otrzymano
2010-09-14
poprawiono
2011-05-10
zaakceptowano
2011-05-11
Twórcy
  • LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
  • LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
Bibliografia
  • [1] M. Borowiecki, On a minimaximal kernel of trees, Discuss. Math. 1 (1975) 3-6.
  • [2] M. Chellali, O. Favaron, A. Hansberg and L. Volkmann, k-domination and k-independence in graphs: A Survey, Graphs and Combinatorics, 28 (2012) 1-55, doi: 10.1007/s00373-011-1040-3.
  • [3] O. Favaron, On a conjecture of Fink and Jacobson concerning k-domination and k-dependence, J. Combinat. Theory (B) 39 (1985) 101-102, doi: 10.1016/0095-8956(85)90040-1.
  • [4] J.F. Fink and M.S. Jacobson, n-domination in graphs, in: Graph Theory with Applications to Algorithms and Computer Science., ed(s), Y. Alavi and A.J. Schwenk (Wiley, New York, 1985) 283-300.
  • [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs ( Marcel Dekker, New York, 1998).
  • [6] 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_1603
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ć.