Critical concepts in domination. (English) Zbl 0725.05049

[For the entire collection see Zbl 0716.00005.]
The paper studies domination critical and domination perfect graphs. A graph is domination critical, if its domination number is k and decreases after adding any new edge. A graph is domination perfect, if the domination number of any of its subgraphs is equal to its independent domination number, i.e. the minimum number of vertices of a set which is simultaneously independent and dominating in G. Various properties of 3- critical graphs are described; degree sequences and diameters of such graphs are investigated. At the end some theorems on domination perfect graphs are proved, among them a theorem characterizing planar domination perfect graphs by means of forbidden induced subgraphs.


05C35 Extremal problems in graph theory


Zbl 0716.00005
Full Text: DOI


[1] B.D. Acharya and H.B. Walikar, Domination critical graphs, preprint. · Zbl 0401.05056
[2] Allan, R.B.; Laskar, R., On domination and independent domination numbers of a graph, Discrete math., 23, 73-76, (1978) · Zbl 0416.05064
[3] D. Bauer, F. Harary, J. Nieminen and C. Suffel, Domination alteration sets in graphs, preprint. · Zbl 0524.05040
[4] Blitch, P., Domination in graphs, Dissertation univ. of S. C., (1983) · Zbl 0512.05055
[5] Bolobás, B.; Cockayne, E.J., Graph theoretic parameters concerning domination, independence, and irredundace, J. graph theory, 3, 271-278, (1979)
[6] Chvátal, V., Tough graphs and Hamiltonian circuits, Discrete math., 2, 215-228, (1973) · Zbl 0256.05122
[7] Cockayne, E.J., Domination in undirected graphs, () · Zbl 0384.05052
[8] Meir, A.; Moon, J.W., Relations between packing and covering numbers of a tree, Pacific J. math., 61, 225-233, (1975) · Zbl 0315.05102
[9] Nebesky, L., On the existence of 1-factors in partial squares of graphs, Czechoslovak math. J., 29, 349-352, (1979) · Zbl 0403.05061
[10] Nieminen, J., Two bounds for the domination number of a graph, J. inst. maths. applics, 14, 183-187, (1974) · Zbl 0288.05124
[11] D.P. Sumner and J.I. Moore, Domination perfect graphs, preprint.
[12] Sumner, D.P.; Blitch, P., Domination critical graphs, J. combin. theory ser. B, 34, 65-76, (1983) · Zbl 0512.05055
[13] Sumner, D.P., 1-factors and antifactors sets, J. London math. soc., 13, 2, 351-359, (1976) · Zbl 0338.05118
[14] W.T. Trotter, personal communication.
[15] Vizing, V.G., A bound on the external stability number of a graph, Dokl. akad. nauk., 164, 729-731, (1965) · Zbl 0136.44703
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.