Relations between edge removing and edge subdivision concerning domination number of a graph

Abstract

Let $e$ be an edge of a connected simple graph $G$. The graph obtained by removing (subdividing) an edge $e$ from $G$ is denoted by $G-e$ ($G_e$). As usual, $\gamma (G)$ denotes the domination number of $G$. We call $G$ an SR-graph if $\gamma (G-e)=\gamma (G_e)$ for any edge $e$ of $G$, and $G$ is an ASR-graph if $\gamma (G-e)\ne (G_e)$ for any edge $e$ of $G$. In this work we give several examples of SR and ASR-graphs. Also, we characterize SR-trees and show that ASR-graphs are $\gamma$-insensitive.

14 pages, 1 figure, 9 references