DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 24(2) (2004) 239-248
DOI: 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