Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
dominating set; domination number; bondage number; additive graph property; hereditary graph property; induced-hereditary graph property
dominating set; domination number; bondage number; additive graph property; hereditary graph property; induced-hereditary graph property
Summary:
In this paper we present results on changing and unchanging of the domination number with respect to the nondegenerate property $\mathcal {P}$, denoted by $\gamma _{\mathcal {P}} (G)$, when a graph $G$ is modified by deleting a vertex or deleting edges. A graph $G$ is $(\gamma _{\mathcal {P}}(G), k)_{\mathcal {P}}$-critical if $\gamma _{\mathcal {P}} (G-S) < \gamma _{\mathcal {P}} (G)$ for any set $S \subsetneq V(G)$ with $|S|=k$. Properties of $(\gamma _{\mathcal {P}}, k)_{\mathcal {P}}$-critical graphs are studied. The plus bondage number with respect to the property $\mathcal {P}$, denoted $b_{\mathcal {P}}^+ (G)$, is the cardinality of the smallest set of edges $U \subseteq E(G)$ such that $\gamma _{\mathcal {P}} (G-U) >\gamma _{\mathcal {P}} (G)$. Some known results for ordinary domination and bondage numbers are extended to $\gamma _{\mathcal {P}} (G)$ and $b_{\mathcal {P}}^+ (G)$. Conjectures concerning $b_{\mathcal {P}}^+ (G)$ are posed.
References:
[1] Ao, S.: Independent domination critical graphs. Master's Dissertation, University of Victoria (1994).
[2] Bange, D., Barkauskas, A., Slater, P.: Efficient Dominating Sets in Graphs. Applications of Discrete Mathematics. R. D. Ringeisen, F. S. Roberts SIAM, Philadelphia, PA (1988), 189-199. MR 0974633
[3] Bauer, D., Harary, F., Nieminen, J., Suffel, S.: Domination alteration sets in graphs. Discrete Math. 47 (1983), 153-161. DOI 10.1016/0012-365X(83)90085-7 | MR 0724653 | Zbl 0524.05040
[4] Brigham, R., Chinn, P., Dutton, R.: Vertex domination-critical graphs. Networks 18 (1988), 173-179. DOI 10.1002/net.3230180304 | MR 0953920 | Zbl 0658.05042
[5] Brigham, R., Haynes, T., Henning, M., Rall, D.: Bicritical domination. Discrete Math. 305 (2005), 18-32. DOI 10.1016/j.disc.2005.09.013 | MR 2186680 | Zbl 1078.05062
[6] Fricke, G., Haynes, T., Hedetniemi, S., Hedetniemi, S., Laskar, R.: Excellent trees. Bull. Inst. Comb. Appl. 34 (2002), 27-38. MR 1880562 | Zbl 0995.05036
[7] Fulman, J., Hanson, D., MacGillivray, G.: Vertex domination-critical graphs. Networks 25 (1995), 41-43. DOI 10.1002/net.3230250203 | MR 1321108 | Zbl 0820.05038
[8] Goddard, W., Haynes, T., Knisley, D.: Hereditary domination and independence parameters. Discuss. Math. Graph Theory 24 (2004), 239-248. DOI 10.7151/dmgt.1228 | MR 2120566 | Zbl 1065.05069
[9] Hartnel, B., Rall, D.: Bounds on the bondage number of a graph. Discrete Math. 128 (1994), 173-177. DOI 10.1016/0012-365X(94)90111-2 | MR 1271863
[10] Haynes, T., Hedetniemi, S., Slater, P.: Fundamentals of domination in graphs. Marcel Dekker, New York, NY (1998). MR 1605684 | Zbl 0890.05002
[11] Michalak, D.: 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
[12] Mojdeh, D., Firoozi, P.: Characteristics of $(\gamma,3)$-critical graphs. Appl. Anal. Discrete Math. 4 (2010), 197-206. DOI 10.2298/AADM100206013M | MR 2654940 | Zbl 1265.05468
[13] Mojdeh, D., Firoozi, P., Hasni, R.: On connected $(\gamma,k)$-critical graphs. Australas. J. Comb. 46 (2010), 25-35. MR 2598690 | Zbl 1196.05064
[14] Samodivkin, V.: Domination with respect to nondegenerate and hereditary properties. Math. Bohem. 133 (2008), 167-178. MR 2428312 | Zbl 1199.05269
[15] Samodivkin, V.: Changing and unchanging of the domination number of a graph. Discrete Math. 308 (2008), 5015-5025. DOI 10.1016/j.disc.2007.08.088 | MR 2450438 | Zbl 1157.05044
[16] Samodivkin, V.: The bondage number of graphs: good and bad vertices. Discuss. Math., Graph Theory 28 (2008), 453-462. DOI 10.7151/dmgt.1419 | MR 2514202 | Zbl 1173.05037
[17] Samodivkin, V.: Domination with respect to nondegenerate properties: bondage number. Australas. J. Comb. 45 (2009), 217-226. MR 2554536 | Zbl 1207.05145
[18] Sampathkumar, E., Neeralagi, P.: Domination and neighborhood critical fixed, free and totally free points. Sankhy\=a 54 (1992), 403-407. MR 1234719
[19] Sumner, D., Wojcicka, E.: Graphs critical with respect to the domination number. Domination in Graphs: Advanced Topics. T. Haynes, S. T. Hedetniemi, P. Slater Marcel Dekker, New York (1998), 471-489. MR 1605701
[20] Teschner, U.: A new upper bound for the bondage number of a graphs with small domination number. Australas. J. Comb. 12 (1995), 27-35. MR 1349195
[21] Teschner, U.: The bondage number of a graphs $G$ can be much greater than $\Delta (G)$. Ars Comb. 43 (1996), 81-87. MR 1415976
[22] Walikar, H., Acharya, B.: Domination critical graphs. Nat. Acad. Sci. Lett. 2 (1979), 70-72. Zbl 0401.05056
Search
Partner of
