Advanced Search

The domination number γ(G) of a graph G is the minimum number of vertices in a set D such that every vertex of the graph is either in D or is adjacent to a member of D. Any dominating set D of a graph G with |D| = γ(G) is called a γ-set of G. A vertex x of a graph G is called: (i) γ-good if x belongs to some γ-set and (ii) γ-bad if x belongs to no γ-set. The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination...

For a graph property $𝒫$ and a graph $G$, we define the domination subdivision number with respect to the property $𝒫$ to be the minimum number of edges that must be subdivided (where each edge in $G$ can be subdivided at most once) in order to change the domination number with respect to the property $𝒫$. In this paper we obtain upper bounds in terms of maximum degree and orientable/non-orientable genus for the domination subdivision number with respect to an induced-hereditary property, total domination...

In this paper we present results on changing and unchanging of the domination number with respect to the nondegenerate property $𝒫$, denoted by ${\gamma }_{𝒫}\left(G\right)$, when a graph $G$ is modified by deleting a vertex or deleting edges. A graph $G$ is ${({\gamma }_{𝒫}\left(G\right),k)}_{𝒫}$-critical if ${\gamma }_{𝒫}(G-S)<{\gamma }_{𝒫}\left(G\right)$ for any set $S⊊V\left(G\right)$ with $\left|S\right|=k$. Properties of ${({\gamma }_{𝒫},k)}_{𝒫}$-critical graphs are studied. The plus bondage number with respect to the property $𝒫$, denoted $b_{𝒫}^{+}\left(G\right)$, is the cardinality of the smallest set of edges $U\subseteq E\left(G\right)$ such that ${\gamma }_{𝒫}(G-U)>{\gamma }_{𝒫}\left(G\right)$. Some known results for ordinary domination and bondage numbers...

For a graphical property $𝒫$ and a graph $G$, a subset $S$ of vertices of $G$ is a $𝒫$-set if the subgraph induced by $S$ 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.

The paper studies minimal acyclic dominating sets, acyclic domination number and upper acyclic domination number in graphs having cut-vertices.