| Title:
|
Domination with respect to nondegenerate properties: vertex and edge removal (English) |
| Author:
|
Samodivkin, Vladimir |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
138 |
| Issue:
|
1 |
| Year:
|
2013 |
| Pages:
|
75-85 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
dominating set |
| Keyword:
|
domination number |
| Keyword:
|
bondage number |
| Keyword:
|
additive graph property |
| Keyword:
|
hereditary graph property |
| Keyword:
|
induced-hereditary graph property |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1274.05363 |
| idMR:
|
MR3076222 |
| DOI:
|
10.21136/MB.2013.143231 |
| . |
| Date available:
|
2013-03-02T18:55:14Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143231 |
| . |
| Reference:
|
[1] Ao, S.: Independent domination critical graphs.Master's Dissertation, University of Victoria (1994). |
| Reference:
|
[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 |
| Reference:
|
[3] Bauer, D., Harary, F., Nieminen, J., Suffel, S.: Domination alteration sets in graphs.Discrete Math. 47 (1983), 153-161. Zbl 0524.05040, MR 0724653, 10.1016/0012-365X(83)90085-7 |
| Reference:
|
[4] Brigham, R., Chinn, P., Dutton, R.: Vertex domination-critical graphs.Networks 18 (1988), 173-179. Zbl 0658.05042, MR 0953920, 10.1002/net.3230180304 |
| Reference:
|
[5] Brigham, R., Haynes, T., Henning, M., Rall, D.: Bicritical domination.Discrete Math. 305 (2005), 18-32. Zbl 1078.05062, MR 2186680, 10.1016/j.disc.2005.09.013 |
| Reference:
|
[6] Fricke, G., Haynes, T., Hedetniemi, S., Hedetniemi, S., Laskar, R.: Excellent trees.Bull. Inst. Comb. Appl. 34 (2002), 27-38. Zbl 0995.05036, MR 1880562 |
| Reference:
|
[7] Fulman, J., Hanson, D., MacGillivray, G.: Vertex domination-critical graphs.Networks 25 (1995), 41-43. Zbl 0820.05038, MR 1321108, 10.1002/net.3230250203 |
| Reference:
|
[8] Goddard, W., Haynes, T., Knisley, D.: Hereditary domination and independence parameters.Discuss. Math. Graph Theory 24 (2004), 239-248. Zbl 1065.05069, MR 2120566, 10.7151/dmgt.1228 |
| Reference:
|
[9] Hartnel, B., Rall, D.: Bounds on the bondage number of a graph.Discrete Math. 128 (1994), 173-177. MR 1271863, 10.1016/0012-365X(94)90111-2 |
| Reference:
|
[10] Haynes, T., Hedetniemi, S., Slater, P.: Fundamentals of domination in graphs.Marcel Dekker, New York, NY (1998). Zbl 0890.05002, MR 1605684 |
| Reference:
|
[11] Michalak, D.: Domination, independence and irredundance with respect to additive induced-hereditary properties.Discrete Math. 286 (2004), 141-146. MR 2084289, 10.1016/j.disc.2003.11.054 |
| Reference:
|
[12] Mojdeh, D., Firoozi, P.: Characteristics of $(\gamma,3)$-critical graphs.Appl. Anal. Discrete Math. 4 (2010), 197-206. Zbl 1265.05468, MR 2654940, 10.2298/AADM100206013M |
| Reference:
|
[13] Mojdeh, D., Firoozi, P., Hasni, R.: On connected $(\gamma,k)$-critical graphs.Australas. J. Comb. 46 (2010), 25-35. Zbl 1196.05064, MR 2598690 |
| Reference:
|
[14] Samodivkin, V.: Domination with respect to nondegenerate and hereditary properties.Math. Bohem. 133 (2008), 167-178. Zbl 1199.05269, MR 2428312 |
| Reference:
|
[15] Samodivkin, V.: Changing and unchanging of the domination number of a graph.Discrete Math. 308 (2008), 5015-5025. Zbl 1157.05044, MR 2450438, 10.1016/j.disc.2007.08.088 |
| Reference:
|
[16] Samodivkin, V.: The bondage number of graphs: good and bad vertices.Discuss. Math., Graph Theory 28 (2008), 453-462. Zbl 1173.05037, MR 2514202, 10.7151/dmgt.1419 |
| Reference:
|
[17] Samodivkin, V.: Domination with respect to nondegenerate properties: bondage number.Australas. J. Comb. 45 (2009), 217-226. Zbl 1207.05145, MR 2554536 |
| Reference:
|
[18] Sampathkumar, E., Neeralagi, P.: Domination and neighborhood critical fixed, free and totally free points.Sankhy\=a 54 (1992), 403-407. MR 1234719 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[22] Walikar, H., Acharya, B.: Domination critical graphs.Nat. Acad. Sci. Lett. 2 (1979), 70-72. Zbl 0401.05056 |
| . |
