PDF

Discussiones Mathematicae Graph Theory 24(2) (2004) 239-248
DOI: https://doi.org/10.7151/dmgt.1228

HEREDITARY DOMINATION AND INDEPENDENCE PARAMETERS

Wayne Goddard Department of Computer Science Clemson University Clemson SC 29631, USA Department of Computer Science University of Natal Durban 4041, South Africa

Teresa Haynes and Debra Knisley Department of Mathematics East Tennessee State University Johnson City TN 37614, USA

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.

Keywords: domination, hereditary property, independence.

2000 Mathematics Subject Classification: 05C69.

References

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

Received 24 July 2002
Revised 27 January 2003