Generalized Petersen graphs are certain graphs consisting of one quadratic factor. For these graphs some numerical invariants concerning the domination are studied, namely the domatic number $d\left(G\right)$, the total domatic number $d_t\left(G\right)$ and the $k$-ply domatic number $d^k\left(G\right)$ for $k=2$ and $k=3$. Some exact values and some inequalities are stated.

Let V₁, V₂ be a partition of the vertex set in a graph G, and let ${\gamma }_i$ denote the least number of vertices needed in G to dominate $V_i$. We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest possible value...

It is known that the removal of an edge from a graph G cannot decrease a domination number γ(G) and can increase it by at most one. Thus we can write that γ(G) ≤ γ(G-e) ≤ γ(G)+1 when an arbitrary edge e is removed. Here we present similar inequalities for the weakly connected domination number ${\gamma }_w$ and the connected domination number ${\gamma }_c$, i.e., we show that ${\gamma }_w\left(G\right)\le {\gamma }_w(G-e)\le {\gamma }_w\left(G\right)+1$ and ${\gamma }_c\left(G\right)\le {\gamma }_c(G-e)\le {\gamma }_c\left(G\right)+2$ if G and G-e are connected. Additionally we show that ${\gamma }_w\left(G\right)\le {\gamma }_w(G-Eₚ)\le {\gamma }_w\left(G\right)+p-1$ and ${\gamma }_c\left(G\right)\le {\gamma }_c(G-Eₚ)\le {\gamma }_c\left(G\right)+2p-2$ if G and G - Eₚ are connected and Eₚ = E(Hₚ) where Hₚ of order p is a connected...

For any graph $G$, let $V\left(G\right)$ and $E\left(G\right)$ denote the vertex set and the edge set of $G$ respectively. The Boolean function graph $B(G,L(G),\mathrm{N}INC)$ of $G$ is a graph with vertex set $V\left(G\right)\cup E\left(G\right)$ and two vertices in $B(G,L(G),\mathrm{N}INC)$ are adjacent if and only if they correspond to two adjacent vertices of $G$, two adjacent edges of $G$ or to a vertex and an edge not incident to it in $G$. For brevity, this graph is denoted by $B_1\left(G\right)$. In this paper, we determine domination number, independent, connected, total, cycle, point-set, restrained, split and non-split domination...

For any graph $G$, let $V\left(G\right)$ and $E\left(G\right)$ denote the vertex set and the edge set of $G$ respectively. The Boolean function graph $B(G,L(G),\mathrm{N}INC)$ of $G$ is a graph with vertex set $V\left(G\right)\cup E\left(G\right)$ and two vertices in $B(G,L(G),\mathrm{N}INC)$ are adjacent if and only if they correspond to two adjacent vertices of $G$, two adjacent edges of $G$ or to a vertex and an edge not incident to it in $G$. For brevity, this graph is denoted by $B_1\left(G\right)$. In this paper, we determine domination number, independent, connected, total, point-set, restrained, split and non-split domination numbers...

This paper contains a number of estimations of the split domination number and the maximal domination number of a graph with a deleted subset of edges which induces a complete subgraph Kₚ. We discuss noncomplete graphs having or not having hanging vertices. In particular, for p = 2 the edge deleted graphs are considered. The motivation of these problems comes from [2] and [6], where the authors, among other things, gave the lower and upper bounds on irredundance, independence and domination numbers...

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $s{d}_{\gamma }\left(G\right)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that $1\le s{d}_{\gamma }\left(G\right)\le 3$ for any graph G. We give a counterexample to this conjecture. On the other hand, we show...

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.

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...

In a graph a vertex is said to dominate itself and all its neighbors. A double dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. The double domination number of G, denoted ${\gamma }_{\times 2}\left(G\right)$, is the minimum cardinality among all double dominating sets of G. We consider the effects of vertex removal on the double domination number of a graph. A graph G is ${\gamma }_{\times 2}$-vertex critical graph (${\gamma }_{\times 2}$-vertex stable graph, respectively) if the removal of any vertex different from a support...

A path π = (v1, v2, . . . , vk+1) in a graph G = (V,E) is a downhill path if for every i, 1 ≤ i ≤ k, deg(vi) ≥ deg(vi+1), where deg(vi) denotes the degree of vertex vi ∈ V. The downhill domination number equals the minimum cardinality of a set S ⊆ V having the property that every vertex v ∈ V lies on a downhill path originating from some vertex in S. We investigate downhill domination numbers of graphs and give upper bounds. In particular, we show that the downhill domination number of a graph is...