The domination subdivision number $s{d}_{\gamma }\left(G\right)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of adjacent vertices...

The domination number γ(G) of a graph G is the minimum cardinality of a subset D of V(G) with the property that each vertex of V(G)-D is adjacent to at least one vertex of D. For a graph G with n vertices we define ε(G) to be the number of leaves in G minus the number of stems in G, and we define the leaf density ζ(G) to equal ε(G)/n. We prove that for any graph G with no isolated vertex, γ(G) ≤ n(1- ζ(G))/2 and we characterize the extremal graphs for this bound. Similar results are obtained for...

Eternal and m-eternal domination are concerned with using mobile guards to protect a graph against infinite sequences of attacks at vertices. Eternal domination allows one guard to move per attack, whereas more than one guard may move per attack in the m-eternal domination model. Inequality chains consisting of the domination, eternal domination, m-eternal domination, independence, and clique covering numbers of graph are explored in this paper. Among other results, we characterize bipartite and...

The domination game is played on a graph G by two players who alternately take turns by choosing a vertex such that in each turn at least one previously undominated vertex is dominated. The game is over when each vertex becomes dominated. One of the players, namely Dominator, wants to finish the game as soon as possible, while the other one wants to delay the end. The number of turns when Dominator starts the game on G and both players play optimally is the graph invariant γg(G), named the game...

In the domination game on a graph G, the players Dominator and Staller alternately select vertices of G. Each vertex chosen must strictly increase the number of vertices dominated. This process eventually produces a dominating set of G; Dominator aims to minimize the size of this set, while Staller aims to maximize it. The size of the dominating set produced under optimal play is the game domination number of G, denoted by γg(G). Kinnersley, West and Zamani [SIAM J. Discrete Math. 27 (2013) 2090-2107]...

The domatic numbers of a graph $G$ and of its complement $\overline{G}$ were studied by J. E. Dunbar, T. W. Haynes and M. A. Henning. They suggested four open problems. We will solve the following ones: Characterize bipartite graphs $G$ having $d\left(G\right)=d\left(\overline{G}\right)$. Further, we will present a partial solution to the problem: Is it true that if $G$ is a graph satisfying $d\left(G\right)=d\left(\overline{G}\right)$, then $\gamma \left(G\right)=\gamma \left(\overline{G}\right)$? Finally, we prove an existence theorem concerning the total domatic number of a graph and of its complement.

Let G₁ and G₂ be disjoint copies of a graph G, and let f:V(G₁) → V(G₂) be a function. Then a functigraph C(G,f) = (V,E) has the vertex set V = V(G₁) ∪ V(G₂) and the edge set E = E(G₁) ∪ E(G₂) ∪ {uv | u ∈ V(G₁), v ∈ V(G₂),v = f(u)}. A functigraph is a generalization of a permutation graph (also known as a generalized prism) in the sense of Chartrand and Harary. In this paper, we study domination in functigraphs. Let γ(G) denote the domination number of G. It is readily seen that γ(G) ≤ γ(C(G,f))...

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.

The domination number $\left(G\right)$ of a graph $G$ and two its variants are considered, namely the signed domination number ${}_s\left(G\right)$ and the minus domination number ${}^{-}\left(G\right)$. These numerical invariants are compared for graphs in which the degrees of vertices do not exceed 3.

The domination number and the domatic number of a certain special type of Kneser graphs are determined.

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