Geodesic
Domination with respect to nondegenerate properties: vertex and edge removal
Mathematica Bohemica, Tome 138 (2013) no. 1, pp. 75-85

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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.
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.
DOI : 10.21136/MB.2013.143231
Classification : 05C69
Keywords: dominating set; domination number; bondage number; additive graph property; hereditary graph property; induced-hereditary graph property 
Samodivkin, Vladimir. Domination with respect to nondegenerate properties: vertex and edge removal. Mathematica Bohemica, Tome 138 (2013) no. 1, pp. 75-85. doi: 10.21136/MB.2013.143231
@article{10_21136_MB_2013_143231,
     author = {Samodivkin, Vladimir},
     title = {Domination with respect to nondegenerate properties: vertex and edge removal},
     journal = {Mathematica Bohemica},
     pages = {75--85},
     year = {2013},
     volume = {138},
     number = {1},
     doi = {10.21136/MB.2013.143231},
     mrnumber = {3076222},
     zbl = {1274.05363},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2013.143231/}
}
TY  - JOUR
AU  - Samodivkin, Vladimir
TI  - Domination with respect to nondegenerate properties: vertex and edge removal
JO  - Mathematica Bohemica
PY  - 2013
SP  - 75
EP  - 85
VL  - 138
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2013.143231/
DO  - 10.21136/MB.2013.143231
LA  - en
ID  - 10_21136_MB_2013_143231
ER  - 
%0 Journal Article
%A Samodivkin, Vladimir
%T Domination with respect to nondegenerate properties: vertex and edge removal
%J Mathematica Bohemica
%D 2013
%P 75-85
%V 138
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2013.143231/
%R 10.21136/MB.2013.143231
%G en
%F 10_21136_MB_2013_143231

[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

[3] Bauer, D., Harary, F., Nieminen, J., Suffel, S.: Domination alteration sets in graphs. Discrete Math. 47 (1983), 153-161. | DOI | MR | Zbl

[4] Brigham, R., Chinn, P., Dutton, R.: Vertex domination-critical graphs. Networks 18 (1988), 173-179. | DOI | MR | Zbl

[5] Brigham, R., Haynes, T., Henning, M., Rall, D.: Bicritical domination. Discrete Math. 305 (2005), 18-32. | DOI | MR | Zbl

[6] Fricke, G., Haynes, T., Hedetniemi, S., Hedetniemi, S., Laskar, R.: Excellent trees. Bull. Inst. Comb. Appl. 34 (2002), 27-38. | MR | Zbl

[7] Fulman, J., Hanson, D., MacGillivray, G.: Vertex domination-critical graphs. Networks 25 (1995), 41-43. | DOI | MR | Zbl

[8] Goddard, W., Haynes, T., Knisley, D.: Hereditary domination and independence parameters. Discuss. Math. Graph Theory 24 (2004), 239-248. | DOI | MR | Zbl

[9] Hartnel, B., Rall, D.: Bounds on the bondage number of a graph. Discrete Math. 128 (1994), 173-177. | DOI | MR

[10] Haynes, T., Hedetniemi, S., Slater, P.: Fundamentals of domination in graphs. Marcel Dekker, New York, NY (1998). | MR | Zbl

[11] Michalak, D.: Domination, independence and irredundance with respect to additive induced-hereditary properties. Discrete Math. 286 (2004), 141-146. | DOI | MR

[12] Mojdeh, D., Firoozi, P.: Characteristics of $(\gamma,3)$-critical graphs. Appl. Anal. Discrete Math. 4 (2010), 197-206. | DOI | MR | Zbl

[13] Mojdeh, D., Firoozi, P., Hasni, R.: On connected $(\gamma,k)$-critical graphs. Australas. J. Comb. 46 (2010), 25-35. | MR | Zbl

[14] Samodivkin, V.: Domination with respect to nondegenerate and hereditary properties. Math. Bohem. 133 (2008), 167-178. | MR | Zbl

[15] Samodivkin, V.: Changing and unchanging of the domination number of a graph. Discrete Math. 308 (2008), 5015-5025. | DOI | MR | Zbl

[16] Samodivkin, V.: The bondage number of graphs: good and bad vertices. Discuss. Math., Graph Theory 28 (2008), 453-462. | DOI | MR | Zbl

[17] Samodivkin, V.: Domination with respect to nondegenerate properties: bondage number. Australas. J. Comb. 45 (2009), 217-226. | MR | Zbl

[18] Sampathkumar, E., Neeralagi, P.: Domination and neighborhood critical fixed, free and totally free points. Sankhy\=a 54 (1992), 403-407. | MR

[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

[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

[21] Teschner, U.: The bondage number of a graphs $G$ can be much greater than $\Delta (G)$. Ars Comb. 43 (1996), 81-87. | MR

[22] Walikar, H., Acharya, B.: Domination critical graphs. Nat. Acad. Sci. Lett. 2 (1979), 70-72. | Zbl

Cité par Sources :