Domination Critical Graphs upon Edge Subdivision

Abstract

A set of vertices $S$ in a graph $G$ is a dominating set if any vertex of $G–S$ is adjacent to some vertex in $S$. The domination number, $\gamma (G)$, of $G$ is the minimum cardinality of a dominating set of $G$.

The subdivision of an edge $uv$ is the operation of replacing $uv$ with a path $uwv$ through a new vertex $w$. A graph $G$ is domination critical upon edge subdivision if the domination number increases by subdivision of any edge.

In this paper, we study domination critical graphs upon edge subdivision. We present several properties and bounds for these graphs and then give a constructive characterization of domination critical trees upon edge subdivision.