| Title:
|
Domination with respect to nondegenerate and hereditary properties (English) |
| Author:
|
Samodivkin, Vladimir |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
133 |
| Issue:
|
2 |
| Year:
|
2008 |
| Pages:
|
167-178 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
domination |
| Keyword:
|
independent domination |
| Keyword:
|
acyclic domination |
| Keyword:
|
good vertex |
| Keyword:
|
bad vertex |
| Keyword:
|
fixed vertex |
| Keyword:
|
free vertex |
| Keyword:
|
hereditary graph property |
| Keyword:
|
induced-hereditary graph property |
| Keyword:
|
nondegenerate graph property |
| Keyword:
|
additive graph property |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1199.05269 |
| idMR:
|
MR2428312 |
| DOI:
|
10.21136/MB.2008.134058 |
| . |
| Date available:
|
2009-09-24T22:35:53Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/134058 |
| . |
| Reference:
|
[1] R. C. Brigham, P. Z. Chinn, R. D. Dutton: Vertex domination-critical graphs.Networks 18 (1988), 173–179. MR 0953920, 10.1002/net.3230180304 |
| Reference:
|
[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 1111839 |
| Reference:
|
[3] Xue-Gang Chen, Liang Sun, De-Xiang Ma: Connected domination critical graphs.Appl. Math. Letters 17 (2004), 503–507. MR 2057342, 10.1016/S0893-9659(04)90118-8 |
| Reference:
|
[4] O. Favaron, D. Sumner, E. Wojcicka: The diameter of domination $k$-critical graphs.J. Graph Theory 18 (1994), 723–734. MR 1297193, 10.1002/jgt.3190180708 |
| Reference:
|
[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 1880562 |
| Reference:
|
[6] J. Fulman, D. Hanson, G. MacGillivray: Vertex domination-critical graphs.Networks 25 (1995), 41–43. MR 1321108, 10.1002/net.3230250203 |
| Reference:
|
[7] W. Goddard, T. Haynes, D. Knisley: Hereditary domination and independence parameters.Discuss. Math. Graph Theory. 24 (2004), 239–248. MR 2120566, 10.7151/dmgt.1228 |
| Reference:
|
[8] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Domination in Graphs.Marcel Dekker, Inc., New York, NY, 1998. MR 1605685 |
| Reference:
|
[9] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Domination in Graphs: Advanced Topics.Marcel Dekker, Inc., New York, NY, 1998. MR 1605685 |
| Reference:
|
[10] S. M. Hedetniemi, S. T. Hedetniemi, D. F. Rall: Acyclic domination.Discrete Math. 222 (2000), 151–165. MR 1771395, 10.1016/S0012-365X(00)00012-1 |
| Reference:
|
[11] T. W. Haynes, M. A. Henning: Changing and unchanging domination: a classification.Discrete Math. 272 (2003), 65–79. MR 2019201, 10.1016/S0012-365X(03)00185-7 |
| Reference:
|
[12] D. Michalak: 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:
|
[13] O. Ore: Theory of Graphs.Amer. Math. Soc. Providence, RI, 1962. Zbl 0105.35401 |
| Reference:
|
[14] V. D. Samodivkin: Minimal acyclic dominating sets and cut-vertices.Math. Bohem. 130 (2005), 81–88. Zbl 1112.05080, MR 2128361 |
| Reference:
|
[15] V. D. Samodivkin: Partitioned graphs and domination related parameters.Annuaire Univ. Sofia Fac. Math. Inform. 97 (2005), 89–96. MR 2191872 |
| Reference:
|
[16] E. Sampathkumar, P. S. Neeralagi: Domination and neighborhood critical fixed, free and totally free points.Sankhyā 54 (1992), 403–407. MR 1234719 |
| Reference:
|
[17] D. P. Sumner, P. Blitch: Domination critical graphs.J. Combin. Theory Ser. B 34 (1983), 65–76. MR 0701172, 10.1016/0095-8956(83)90007-2 |
| Reference:
|
[18] P. D. Vestergaard, B. Zelinka: Cut-vertices and domination in graphs.Math. Bohem. 120 (1995), 135–143. MR 1357598 |
| . |
