Domination with respect to nondegenerate
and hereditary properties

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.

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

Classification (MSC2000): 05C69

Full text of the article:

• Compressed PostScript file (148 kilobytes)
• PDF file (160 kilobytes)