Boundary domination in graphs

KM. Kathiresan ; G. Marimuthu ; M. Sivanandha Saraswathy

Kragujevac Journal of Mathematics, Tome 33 (2010) no. 1.

Résumé

Let $G$ be a nontrivial connected graph. The distance between two vertices $u$ and $v$ of $G$ is the length of a shortest $u-v$ path in $G$. Let $u$ be a vertex in $G$. A vertex $v$ is an eccentric vertex of $u$ if $d(u,v)=e(u)$, that is every vertex at greatest distance from $u$ is an eccentric vertex of $u$. A vertex $v$ is an eccentric vertex of $G$ if $v$ is an eccentric vertex of some vertex of $G$. Consequently, if $v$ is an eccentric vertex of $u$ and $w$ is a neighbor of $v$, then $d(u,w)eq d(u,v)$. A vertex $v$ may have this property, however, without being an eccentric vertex of $u$. A vertex $v$ is a boundary vertex of a vertex $u$ if $d(u,w)eq d(u,v)$ for all $wn N(v)$. A vertex $u$ may have more than one boundary vertex at different distance levels. A vertex $v$ is called a boundary neighbor of $u$ if $v$ is a nearest boundary of $u$. The number of boundary neighbors of a vertex $u$ is called the boundary degree of $u$. In this paper, first we show that there is no relationship between the traditional degree and the boundary degree of a vertex. Finally we define boundary dominating set for a graph and we give an upper bound for the boundary domination number of a graph.