Article in press
Authors:
Title:
Domination in graphs and the removal of a matching
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-04-07 , Revised: 2023-08-20 , Accepted: 2023-08-21 , Available online: 2023-09-21 , https://doi.org/10.7151/dmgt.2516
Abstract:
We consider how the domination number of an undirected graph changes on the
removal of a maximal matching. It is straightforward that there are graphs where
no matching removal increases the domination number, and where some matching
removal doubles the domination number. We show that in a nontrivial tree there
is always a matching removal that increases the domination number; and if a
graph has domination number at least $2$ there is always a maximal matching
removal that does not double the domination number. We show that these results
are sharp and discuss related questions.
Keywords:
domination, matching, edge removal, trees
References:
- B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979) 241–249.
https://doi.org/10.1002/jgt.3190030306 - R.C. Brigham, P.Z. Chinn and R.D. Dutton, Vertex domination-critical graphs, Networks 18 (1988) 173–179.
https://doi.org/10.1002/net.3230180304 - J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, The bondage number of a graph, Discrete Math. 86 (1990) 47–57.
https://doi.org/10.1016/0012-365X(90)90348-L - G. Gunther, B. Hartnell, L.R. Markus and D. Rall, Graphs with unique minimum dominating sets, Congr. Numer. 101 (1994) 55–63.
- D.P Sumner, Critical concepts in domination, Discrete Math. 86 (1990) 33–46.
https://doi.org/10.1016/0012-365X(90)90347-K - U. Teschner, New results about the bondage number of a graph, Discrete Math. 171 (1997) 249–259.
https://doi.org/10.1016/S0012-365X(96)00007-6
Close