Domination with respect to nondegenerate properties: vertex and edge removal

Vladimir D. Samodivkin

Mathematica Bohemica (2013)

  • Volume: 138, Issue: 1, page 75-85
  • ISSN: 0862-7959

Abstract

top
In this paper we present results on changing and unchanging of the domination number with respect to the nondegenerate property 𝒫 , denoted by γ 𝒫 ( G ) , when a graph G is modified by deleting a vertex or deleting edges. A graph G is ( γ 𝒫 ( G ) , k ) 𝒫 -critical if γ 𝒫 ( G - S ) < γ 𝒫 ( G ) for any set S ⊊ V ( G ) with | S | = k . Properties of ( γ 𝒫 , k ) 𝒫 -critical graphs are studied. The plus bondage number with respect to the property 𝒫 , denoted b 𝒫 + ( G ) , is the cardinality of the smallest set of edges U ⊆ E ( G ) such that γ 𝒫 ( G - U ) > γ 𝒫 ( G ) . Some known results for ordinary domination and bondage numbers are extended to γ 𝒫 ( G ) and b 𝒫 + ( G ) . Conjectures concerning b 𝒫 + ( G ) are posed.

How to cite

top

Samodivkin, Vladimir D.. "Domination with respect to nondegenerate properties: vertex and edge removal." Mathematica Bohemica 138.1 (2013): 75-85. <http://eudml.org/doc/252550>.

@article{Samodivkin2013,
abstract = {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.},
author = {Samodivkin, Vladimir D.},
journal = {Mathematica Bohemica},
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; vertex deletion; edge deletion},
language = {eng},
number = {1},
pages = {75-85},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Domination with respect to nondegenerate properties: vertex and edge removal},
url = {http://eudml.org/doc/252550},
volume = {138},
year = {2013},
}

TY - JOUR
AU - Samodivkin, Vladimir D.
TI - Domination with respect to nondegenerate properties: vertex and edge removal
JO - Mathematica Bohemica
PY - 2013
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 138
IS - 1
SP - 75
EP - 85
AB - 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.
LA - eng
KW - 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; vertex deletion; edge deletion
UR - http://eudml.org/doc/252550
ER -

References

top
  1. Ao, S., Independent domination critical graphs, Master's Dissertation, University of Victoria (1994). (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. (1988) MR0974633
  3. Bauer, D., Harary, F., Nieminen, J., Suffel, S., 10.1016/0012-365X(83)90085-7, Discrete Math. 47 (1983), 153-161. (1983) Zbl0524.05040MR0724653DOI10.1016/0012-365X(83)90085-7
  4. Brigham, R., Chinn, P., Dutton, R., 10.1002/net.3230180304, Networks 18 (1988), 173-179. (1988) Zbl0658.05042MR0953920DOI10.1002/net.3230180304
  5. Brigham, R., Haynes, T., Henning, M., Rall, D., 10.1016/j.disc.2005.09.013, Discrete Math. 305 (2005), 18-32. (2005) Zbl1078.05062MR2186680DOI10.1016/j.disc.2005.09.013
  6. Fricke, G., Haynes, T., Hedetniemi, S., Hedetniemi, S., Laskar, R., Excellent trees, Bull. Inst. Comb. Appl. 34 (2002), 27-38. (2002) Zbl0995.05036MR1880562
  7. Fulman, J., Hanson, D., MacGillivray, G., 10.1002/net.3230250203, Networks 25 (1995), 41-43. (1995) Zbl0820.05038MR1321108DOI10.1002/net.3230250203
  8. Goddard, W., Haynes, T., Knisley, D., 10.7151/dmgt.1228, Discuss. Math. Graph Theory 24 (2004), 239-248. (2004) Zbl1065.05069MR2120566DOI10.7151/dmgt.1228
  9. Hartnel, B., Rall, D., 10.1016/0012-365X(94)90111-2, Discrete Math. 128 (1994), 173-177. (1994) MR1271863DOI10.1016/0012-365X(94)90111-2
  10. Haynes, T., Hedetniemi, S., Slater, P., Fundamentals of domination in graphs, Marcel Dekker, New York, NY (1998). (1998) Zbl0890.05002MR1605684
  11. Michalak, D., 10.1016/j.disc.2003.11.054, Discrete Math. 286 (2004), 141-146. (2004) MR2084289DOI10.1016/j.disc.2003.11.054
  12. Mojdeh, D., Firoozi, P., 10.2298/AADM100206013M, Appl. Anal. Discrete Math. 4 (2010), 197-206. (2010) Zbl1265.05468MR2654940DOI10.2298/AADM100206013M
  13. Mojdeh, D., Firoozi, P., Hasni, R., On connected ( γ , k ) -critical graphs, Australas. J. Comb. 46 (2010), 25-35. (2010) Zbl1196.05064MR2598690
  14. Samodivkin, V., Domination with respect to nondegenerate and hereditary properties, Math. Bohem. 133 (2008), 167-178. (2008) Zbl1199.05269MR2428312
  15. Samodivkin, V., 10.1016/j.disc.2007.08.088, Discrete Math. 308 (2008), 5015-5025. (2008) Zbl1157.05044MR2450438DOI10.1016/j.disc.2007.08.088
  16. Samodivkin, V., 10.7151/dmgt.1419, Discuss. Math., Graph Theory 28 (2008), 453-462. (2008) Zbl1173.05037MR2514202DOI10.7151/dmgt.1419
  17. Samodivkin, V., Domination with respect to nondegenerate properties: bondage number, Australas. J. Comb. 45 (2009), 217-226. (2009) Zbl1207.05145MR2554536
  18. Sampathkumar, E., Neeralagi, P., Domination and neighborhood critical fixed, free and totally free points, Sankhyā 54 (1992), 403-407. (1992) MR1234719
  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. (1998) MR1605701
  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. (1995) MR1349195
  21. Teschner, U., The bondage number of a graphs G can be much greater than Δ ( G ) , Ars Comb. 43 (1996), 81-87. (1996) MR1415976
  22. Walikar, H., Acharya, B., Domination critical graphs, Nat. Acad. Sci. Lett. 2 (1979), 70-72. (1979) Zbl0401.05056

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.