Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
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
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
Summary:
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.
References:
[1] R. C. Brigham, P. Z. Chinn, R. D. Dutton: Vertex domination-critical graphs. Networks 18 (1988), 173–179. DOI 10.1002/net.3230180304 | 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. DOI 10.1016/S0893-9659(04)90118-8 | MR 2057342
[4] O. Favaron, D. Sumner, E. Wojcicka: The diameter of domination $k$-critical graphs. J. Graph Theory 18 (1994), 723–734. DOI 10.1002/jgt.3190180708 | 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. DOI 10.1002/net.3230250203 | MR 1321108
[7] W. Goddard, T. Haynes, D. Knisley: Hereditary domination and independence parameters. Discuss. Math. Graph Theory. 24 (2004), 239–248. DOI 10.7151/dmgt.1228 | 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. DOI 10.1016/S0012-365X(00)00012-1 | MR 1771395
[11] T. W. Haynes, M. A. Henning: Changing and unchanging domination: a classification. Discrete Math. 272 (2003), 65–79. DOI 10.1016/S0012-365X(03)00185-7 | MR 2019201
[12] D. Michalak: Domination, independence and irredundance with respect to additive induced-hereditary properties. Discrete Math. 286 (2004), 141–146. DOI 10.1016/j.disc.2003.11.054 | 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. DOI 10.1016/0095-8956(83)90007-2 | MR 0701172
[18] P. D. Vestergaard, B. Zelinka: Cut-vertices and domination in graphs. Math. Bohem. 120 (1995), 135–143. MR 1357598
Search
Partner of
