Changing and Unchanging of the Domination Number of a Graph: Path Addition Numbers

Given a graph $G=(V, E)$ and two its distinct vertices $u$ and $v$, the $(u, v)$-$P_k$-addition graph of $G$ is the graph $G_{u,v,k−2}$ obtained from disjoint union of $G$ and a path $P_k : x_0, x_1,...,x_{k−1}, k ≥ 2$, by identifying the vertices $u$ and $x_0$, and identifying the vertices $v$ and $x_{k−1}$. We prove that $\gamma(G) − 1 ≤ \gamma(G_{u,v,k})$ for all $k ≥ 1$, and $\gamma(G_{u,v,k})>\gamma(G)$ when $k ≥ 5$. We also provide necessary and sufficient conditions for the equality $\gamma(G_{u,v,k})=\gamma(G)$ to be valid for each pair $u, v ∈ V(G)$. In addition, we establish sharp upper and lower bounds for the minimum, respectively maximum, $k$ in a graph $G$ over all pairs of vertices $u$ and $v$ in $G$ such that the $(u, v)$-$P_k$-addition graph of $G$ has a larger domination number than $G$, which we consider separately for adjacent and non-adjacent pairs of vertices.