ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


V. Samodivkin


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


Discussiones Mathematicae Graph Theory

Received: 2018-01-15, Revised: 2018-11-02, Accepted: 2018-11-03,


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,\dots,x_{k-1}$, $k \geq 2$, by identifying the vertices $u$ and $x_0$, and identifying the vertices $v$ and $x_{k-1}$. We prove that $\gamma(G)-1 \leq \gamma(G_{u,v,k})$ for all $k \geq 1$, and $\gamma(G_{u,v,k})>\gamma(G)$ when $k \geq 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)$. 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.


domination number, path addition