PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2004 | 24 | 2 | 239-248
Tytuł artykułu

Hereditary domination and independence parameters

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
For a graphical property P and a graph G, we say that a subset S of the vertices of G is a P-set if the subgraph induced by S has the property P. Then the P-domination number of G is the minimum cardinality of a dominating P-set and the P-independence number the maximum cardinality of a P-set. We show that several properties of domination, independent domination and acyclic domination hold for arbitrary properties P that are closed under disjoint unions and subgraphs.
Słowa kluczowe
Wydawca
Rocznik
Tom
24
Numer
2
Strony
239-248
Opis fizyczny
Daty
wydano
2004
Twórcy
  • Department of Computer Science, Clemson University, Clemson SC 29631, USA
  • Department of Computer Science, University of Natal, Durban 4041, South Africa
  • Department of Mathematics, East Tennessee State University, Johnson City TN 37614, USA
  • Department of Mathematics, East Tennessee State University, Johnson City TN 37614, USA
Bibliografia
  • [1] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
  • [2] M. Borowiecki, D. Michalak and E. Sidorowicz, Generalized domination, independence and irredundance, Discuss. Math. Graph Theory 17 (1997) 143-153, doi: 10.7151/dmgt.1048.
  • [3] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: Advances in Graph Theory (Vishwa, 1991) 41-68.
  • [4] M.R. Garey and D.S. Johnson, Computers and Intractability (W H Freeman, 1979).
  • [5] J. Gimbel and P.D. Vestergaard, Inequalities for total matchings of graphs, Ars Combin. 39 (1995) 109-119.
  • [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, 1997).
  • [7] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds.) Domination in Graphs: Advanced topics (Marcel Dekker, 1997).
  • [8] T.W. Haynes and M.A. Henning, Path-free domination, J. Combin. Math. Combin. Comput. 33 (2000) 9-21.
  • [9] S.M. Hedetniemi, S.T. Hedetniemi and D.F. Rall, Acyclic domination, Discrete Math. 222 (2000) 151-165, doi: 10.1016/S0012-365X(00)00012-1.
  • [10] D. Michalak, Domination, independence and irredundance with respect to additive induced-hereditary properties, Discrete Math., to appear.
  • [11] C.M. Mynhardt, On the difference between the domination and independent domination number of cubic graphs, in: Graph Theory, Combinatorics, and Applications, Y. Alavi et al. eds, Wiley, 2 (1991) 939-947.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-dmgtv24i2bwm
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ć.