Domination with respect to nondegenerate and hereditary properties

Vladimir D. Samodivkin

Mathematica Bohemica (2008)

  • Volume: 133, Issue: 2, page 167-178
  • ISSN: 0862-7959

Abstract

top
For a graphical property and a graph , a subset of vertices of is a -set if the subgraph induced by has the property . The domination number with respect to the property , is the minimum cardinality of a dominating -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.

How to cite

top

Samodivkin, Vladimir D.. "Domination with respect to nondegenerate and hereditary properties." Mathematica Bohemica 133.2 (2008): 167-178. <http://eudml.org/doc/250519>.

@article{Samodivkin2008,
abstract = {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.},
author = {Samodivkin, Vladimir D.},
journal = {Mathematica Bohemica},
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; domination; independent domination; acyclic domination; good vertex; bad vertex; fixed vertex; free vertex},
language = {eng},
number = {2},
pages = {167-178},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Domination with respect to nondegenerate and hereditary properties},
url = {http://eudml.org/doc/250519},
volume = {133},
year = {2008},
}

TY - JOUR
AU - Samodivkin, Vladimir D.
TI - Domination with respect to nondegenerate and hereditary properties
JO - Mathematica Bohemica
PY - 2008
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 133
IS - 2
SP - 167
EP - 178
AB - 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.
LA - eng
KW - 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; domination; independent domination; acyclic domination; good vertex; bad vertex; fixed vertex; free vertex
UR - http://eudml.org/doc/250519
ER -

References

top
  1. 10.1002/net.3230180304, Networks 18 (1988), 173–179. (1988) MR0953920DOI10.1002/net.3230180304
  2. Changing and unchanging the domination number of a graph, J. Combin. Math. Combin. Comput. 9 (1991), 57–63. (1991) MR1111839
  3. 10.1016/S0893-9659(04)90118-8, Appl. Math. Letters 17 (2004), 503–507. (2004) MR2057342DOI10.1016/S0893-9659(04)90118-8
  4. 10.1002/jgt.3190180708, J. Graph Theory 18 (1994), 723–734. (1994) MR1297193DOI10.1002/jgt.3190180708
  5. Excellent trees, Bull. Inst. Comb. Appl. 34 (2002), 27–38. (2002) MR1880562
  6. 10.1002/net.3230250203, Networks 25 (1995), 41–43. (1995) MR1321108DOI10.1002/net.3230250203
  7. 10.7151/dmgt.1228, Discuss. Math. Graph Theory. 24 (2004), 239–248. (2004) MR2120566DOI10.7151/dmgt.1228
  8. Domination in Graphs, Marcel Dekker, Inc., New York, NY, 1998. (1998) MR1605685
  9. Domination in Graphs: Advanced Topics, Marcel Dekker, Inc., New York, NY, 1998. (1998) MR1605685
  10. 10.1016/S0012-365X(00)00012-1, Discrete Math. 222 (2000), 151–165. (2000) MR1771395DOI10.1016/S0012-365X(00)00012-1
  11. 10.1016/S0012-365X(03)00185-7, Discrete Math. 272 (2003), 65–79. (2003) MR2019201DOI10.1016/S0012-365X(03)00185-7
  12. 10.1016/j.disc.2003.11.054, Discrete Math. 286 (2004), 141–146. (2004) MR2084289DOI10.1016/j.disc.2003.11.054
  13. Theory of Graphs, Amer. Math. Soc. Providence, RI, 1962. (1962) Zbl0105.35401
  14. Minimal acyclic dominating sets and cut-vertices, Math. Bohem. 130 (2005), 81–88. (2005) Zbl1112.05080MR2128361
  15. Partitioned graphs and domination related parameters, Annuaire Univ. Sofia Fac. Math. Inform. 97 (2005), 89–96. (2005) MR2191872
  16. Domination and neighborhood critical fixed, free and totally free points, Sankhyā 54 (1992), 403–407. (1992) MR1234719
  17. 10.1016/0095-8956(83)90007-2, J. Combin. Theory Ser. B 34 (1983), 65–76. (1983) MR0701172DOI10.1016/0095-8956(83)90007-2
  18. Cut-vertices and domination in graphs, Math. Bohem. 120 (1995), 135–143. (1995) MR1357598

NotesEmbed ?

top

You must be logged in to post comments.