Hereditary domination and independence parameters

Wayne Goddard; Teresa Haynes; Debra Knisley

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 2, page 239-248
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Wayne Goddard, Teresa Haynes, and Debra Knisley. "Hereditary domination and independence parameters." Discussiones Mathematicae Graph Theory 24.2 (2004): 239-248. <http://eudml.org/doc/270265>.

@article{WayneGoddard2004,
abstract = {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.},
author = {Wayne Goddard, Teresa Haynes, Debra Knisley},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; hereditary property; independence},
language = {eng},
number = {2},
pages = {239-248},
title = {Hereditary domination and independence parameters},
url = {http://eudml.org/doc/270265},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Wayne Goddard
AU - Teresa Haynes
AU - Debra Knisley
TI - Hereditary domination and independence parameters
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 2
SP - 239
EP - 248
AB - 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.
LA - eng
KW - domination; hereditary property; independence
UR - http://eudml.org/doc/270265
ER -

References

top
  1. [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. Zbl0902.05026
  2. [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. Zbl0904.05045
  3. [3] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: Advances in Graph Theory (Vishwa, 1991) 41-68. 
  4. [4] M.R. Garey and D.S. Johnson, Computers and Intractability (W H Freeman, 1979). 
  5. [5] J. Gimbel and P.D. Vestergaard, Inequalities for total matchings of graphs, Ars Combin. 39 (1995) 109-119. Zbl0837.05085
  6. [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, 1997). Zbl0890.05002
  7. [7] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds.) Domination in Graphs: Advanced topics (Marcel Dekker, 1997). 
  8. [8] T.W. Haynes and M.A. Henning, Path-free domination, J. Combin. Math. Combin. Comput. 33 (2000) 9-21. 
  9. [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. Zbl0961.05052
  10. [10] D. Michalak, Domination, independence and irredundance with respect to additive induced-hereditary properties, Discrete Math., to appear. 
  11. [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. Zbl0840.05038

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.