\input zb-basic
\input zb-ioport
\iteman{io-port 06092030}
\itemau{Desormeaux, Wyatt J.; Hall, Adam J.; Haynes, Teresa W.; Koessler, Denise; Langston, Michael A.; Rickett Stephanie; Scott, Hamilton}
\itemti{Effects of edge lifting on domination in graphs.}
\itemso{Bull. Inst. Comb. Appl. 63, 77-86 (2011).}
\itemab
Summary: Let vertices $u$ and $v$ be at distance two apart in a graph $G$, and let $x$ be a common neighbor of $u$ and $v$. The operation of removing the edges $ux$ and $vx$ from $G$, while adding the edge $uv$ to $G$ is called edge lifting. Here we initiate the study of the effects of edge lifting on the domination number of a graph. We show that an edge lift can change the domination number (either increasing or decreasing it) by at most one. We classify graphs according to the effects of edge lifts on their domination number. Our main result shows that if every edge lift changes the domination number of a graph $G$, then every edge lift of $G$ has the same effect on the domination number. In other words, for such a graph $G$, there is not both an edge lift that decreases and an edge lift that increases the domination number.
\itemrv{~}
\itemcc{}
\itemut{edge splitting; domination number; domination critical graphs}
\itemli{}
\end