Changing and unchanging of the domination number of a graph: Path addition numbers

Abstract

Given a graph $G=(V,E)$ and two its distinct vertices $u$ and $v$. The $(u,v)$-$P_k$-{\em 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\ge 2$, by identifying the vertices $u$ and $x_0$, and identifying the vertices $v$ and $x_{k-1}$. We prove that (a) $\gamma (G)-1\le \gamma (G_{u,v,k})$ for all $k\ge 1$, and (b) $\gamma (G_{u,v,k})>\gamma (G)$ when $k\ge 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\in V(G)$. pair $u,v\in V(G)$.

14 pages, 2 figures