Geodesic
Domination with respect to nondegenerate and hereditary properties
Mathematica Bohemica, Tome 133 (2008) no. 2, pp. 167-178

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

MR Zbl
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.
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.
DOI : 10.21136/MB.2008.134058
Classification : 05C69
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 
Samodivkin, Vladimir. Domination with respect to nondegenerate and hereditary properties. Mathematica Bohemica, Tome 133 (2008) no. 2, pp. 167-178. doi: 10.21136/MB.2008.134058
@article{10_21136_MB_2008_134058,
     author = {Samodivkin, Vladimir},
     title = {Domination with respect to nondegenerate and hereditary properties},
     journal = {Mathematica Bohemica},
     pages = {167--178},
     year = {2008},
     volume = {133},
     number = {2},
     doi = {10.21136/MB.2008.134058},
     mrnumber = {2428312},
     zbl = {1199.05269},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2008.134058/}
}
TY  - JOUR
AU  - Samodivkin, Vladimir
TI  - Domination with respect to nondegenerate and hereditary properties
JO  - Mathematica Bohemica
PY  - 2008
SP  - 167
EP  - 178
VL  - 133
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2008.134058/
DO  - 10.21136/MB.2008.134058
LA  - en
ID  - 10_21136_MB_2008_134058
ER  - 
%0 Journal Article
%A Samodivkin, Vladimir
%T Domination with respect to nondegenerate and hereditary properties
%J Mathematica Bohemica
%D 2008
%P 167-178
%V 133
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2008.134058/
%R 10.21136/MB.2008.134058
%G en
%F 10_21136_MB_2008_134058

[1] R. C. Brigham, P. Z. Chinn, R. D. Dutton: Vertex domination-critical graphs. Networks 18 (1988), 173–179. | DOI | MR

[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

[3] Xue-Gang Chen, Liang Sun, De-Xiang Ma: Connected domination critical graphs. Appl. Math. Letters 17 (2004), 503–507. | DOI | MR

[4] O. Favaron, D. Sumner, E. Wojcicka: The diameter of domination $k$-critical graphs. J. Graph Theory 18 (1994), 723–734. | DOI | MR

[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

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

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

[8] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Domination in Graphs. Marcel Dekker, Inc., New York, NY, 1998. | MR

[9] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Domination in Graphs: Advanced Topics. Marcel Dekker, Inc., New York, NY, 1998. | MR

[10] S. M. Hedetniemi, S. T. Hedetniemi, D. F. Rall: Acyclic domination. Discrete Math. 222 (2000), 151–165. | DOI | MR

[11] T. W. Haynes, M. A. Henning: Changing and unchanging domination: a classification. Discrete Math. 272 (2003), 65–79. | DOI | MR

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

[13] O. Ore: Theory of Graphs. Amer. Math. Soc. Providence, RI, 1962. | Zbl

[14] V. D. Samodivkin: Minimal acyclic dominating sets and cut-vertices. Math. Bohem. 130 (2005), 81–88. | MR | Zbl

[15] V. D. Samodivkin: Partitioned graphs and domination related parameters. Annuaire Univ. Sofia Fac. Math. Inform. 97 (2005), 89–96. | MR

[16] E. Sampathkumar, P. S. Neeralagi: Domination and neighborhood critical fixed, free and totally free points. Sankhyā 54 (1992), 403–407. | MR

[17] D. P. Sumner, P. Blitch: Domination critical graphs. J. Combin. Theory Ser. B 34 (1983), 65–76. | DOI | MR

[18] P. D. Vestergaard, B. Zelinka: Cut-vertices and domination in graphs. Math. Bohem. 120 (1995), 135–143. | MR

Cité par Sources :