Previous |  Up |  Next


domination; independent domination; acyclic domination; good vertex; bad vertex; fixed vertex; free vertex; hereditary graph property; induced-hereditary graph property; nondegenerate graph property; additive graph property
For a graphical property $\mathcal{P}$ and a graph $G$, a subset $S$ of vertices of $G$ is a $\mathcal{P}$-set if the subgraph induced by $S$ has the property $\mathcal{P}$. The domination number with respect to the property $\mathcal{P}$, is the minimum cardinality of a dominating $\mathcal{P}$-set. In this paper we present results on changing and unchanging of the domination number with respect to the nondegenerate and hereditary properties when a graph is modified by adding an edge or deleting a vertex.
[1] R. C. Brigham, P. Z. Chinn, R. D. Dutton: Vertex domination-critical graphs. Networks 18 (1988), 173–179. MR 0953920
[2] J. R. Carrington, F. Harary, T. W. Haynes: Changing and unchanging the domination number of a graph. J. Combin. Math. Combin. Comput. 9 (1991), 57–63. MR 1111839
[3] Xue-Gang Chen, Liang Sun, De-Xiang Ma: Connected domination critical graphs. Appl. Math. Letters 17 (2004), 503–507. MR 2057342
[4] O. Favaron, D. Sumner, E. Wojcicka: The diameter of domination $k$-critical graphs. J. Graph Theory 18 (1994), 723–734. MR 1297193
[5] G. H. Fricke, T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, R. C. Laskar: Excellent trees. Bull. Inst. Comb. Appl. 34 (2002), 27–38. MR 1880562
[6] J. Fulman, D. Hanson, G. MacGillivray: Vertex domination-critical graphs. Networks 25 (1995), 41–43. MR 1321108
[7] W. Goddard, T. Haynes, D. Knisley: Hereditary domination and independence parameters. Discuss. Math. Graph Theory. 24 (2004), 239–248. MR 2120566
[8] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Domination in Graphs. Marcel Dekker, Inc., New York, NY, 1998. MR 1605685
[9] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Domination in Graphs: Advanced Topics. Marcel Dekker, Inc., New York, NY, 1998. MR 1605685
[10] S. M. Hedetniemi, S. T. Hedetniemi, D. F. Rall: Acyclic domination. Discrete Math. 222 (2000), 151–165. MR 1771395
[11] T. W. Haynes, M. A. Henning: Changing and unchanging domination: a classification. Discrete Math. 272 (2003), 65–79. MR 2019201
[12] D. Michalak: Domination, independence and irredundance with respect to additive induced-hereditary properties. Discrete Math. 286 (2004), 141–146. MR 2084289
[13] O. Ore: Theory of Graphs. Amer. Math. Soc. Providence, RI, 1962. Zbl 0105.35401
[14] V. D. Samodivkin: Minimal acyclic dominating sets and cut-vertices. Math. Bohem. 130 (2005), 81–88. MR 2128361 | Zbl 1112.05080
[15] V. D. Samodivkin: Partitioned graphs and domination related parameters. Annuaire Univ. Sofia Fac. Math. Inform. 97 (2005), 89–96. MR 2191872
[16] E. Sampathkumar, P. S. Neeralagi: Domination and neighborhood critical fixed, free and totally free points. Sankhyā 54 (1992), 403–407. MR 1234719
[17] D. P. Sumner, P. Blitch: Domination critical graphs. J. Combin. Theory Ser. B 34 (1983), 65–76. MR 0701172
[18] P. D. Vestergaard, B. Zelinka: Cut-vertices and domination in graphs. Math. Bohem. 120 (1995), 135–143. MR 1357598
Partner of
EuDML logo