×

Domination dot-critical graphs. (English) Zbl 1085.05047

Summary: A graph \(G\) is dot-critical if contracting any edge decreases the domination number. It is totally dot-critical if identifying any two vertices decreases the domination number. We show that the totally dot-critical graphs essentially include the much-studied domination vertex-critical and edge-critical graphs as special cases. We investigate these properties, and provide a characterization of dot-critical and totally dot-critical graphs with domination number 2. We also consider the question of when a dot-critical graph contains a critical vertex.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Keywords:

tree; corona
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R.C. Brigham, P.Z. Chinn, R.D. Dutton, A study of vertex domination critical graphs, Technical Report, University of Central Florida, 1984.; R.C. Brigham, P.Z. Chinn, R.D. Dutton, A study of vertex domination critical graphs, Technical Report, University of Central Florida, 1984. · Zbl 0658.05042
[2] T.A. Burton, Domination dot-critical graphs, Ph.D. Dissertation, University of South Carolina, 2001.; T.A. Burton, Domination dot-critical graphs, Ph.D. Dissertation, University of South Carolina, 2001. · Zbl 1085.05047
[3] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998.; T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998. · Zbl 0890.05002
[4] Sumner, D. P.; Blitch, P., Domination critical graphs, JCT Ser. B, 34, 65-76 (1983) · Zbl 0512.05055
[5] Sumner, D. P.; Wojcicka, E., Graphs critical with respect to the domination number, (Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Domination in Graphs—Advanced Topics (1998)), 439-469 · Zbl 0891.05043
[6] West, D. B., Introduction to Graph Theory (2001), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.