Boundary domination in graphs

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

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.