Opuscula Math. 24, no. 2 (2004), 231-234

Opuscula Mathematica

# Domination parameters of a graph with added vertex

Maciej Zwierzchowski

Abstract. Let $$G=(V,E)$$ be a graph. A subset $$D\subseteq V$$ is a total dominating set of $$G$$ if for every vertex $$y\in V$$ there is a vertex $$x\in D$$ with $$xy\in E$$. A subset $$D\subseteq V$$ is a strong dominating set of $$G$$ if for every vertex $$y\in V-D$$ there is a vertex $$x\in D$$ with $$xy\in E$$ and $$\deg _{G}(x)\geq\deg _{G}(y)$$. The total domination number $$\gamma _{t}(G)$$ (the strong domination number $$\gamma_{S}(G)$$) is defined as the minimum cardinality of a total dominating set (a strong dominating set) of $$G$$. The concept of total domination was first defined by Cockayne, Dawes and Hedetniemi in 1980 [Cockayne E. J., Dawes R. M., Hedetniemi S. T.: Total domination in graphs. Networks 10 (1980), 211–219], while the strong domination was introduced by Sampathkumar and Pushpa Latha in 1996 [Pushpa Latha L., Sampathkumar E.: Strong weak domination and domination balance in a graph. Discrete Mathematics 161 (1996), 235–242]. By a subdivision of an edge $$uv\in E$$ we mean removing edge $$uv$$, adding a new vertex $$x$$, and adding edges $$ux$$ and $$vx$$. A graph obtained from $$G$$ by subdivision an edge $$uv\in E$$ is denoted by $$G\oplus u_{x}v_{x}$$. The behaviour of the total domination number and the strong domination number of a graph $$G\oplus u_{x}v_{x}$$ is developed.

Keywords: the total domination number, the strong domination number, subdivision.

Mathematics Subject Classification: 05C69.

Full text (pdf)