EXPONENTIAL DOMINATION OF TREE RELATED GRAPHS

A. AYTAC 1, B. ATAY ATAKUL2

[PDF]

Abstract

The well-known concept of domination in graphs is a good tool for analyzing situations that can be modeled by networks. Although a vertex in the graph can exert influence on, or dominate, all vertices in its immediate neighbourhood, in some real world situations, this can be change. The vertex can also influence all vertices within a given distance. This situation is characterized by distance domination. The influence of the vertex in the graph doesn't extend beyond its neighbourhood and even this influence decreases with distance. Up to the present, no framework for this situation has been put forward yet. The dominating power of the vertex in the graph decreases exponentially, with distance by the factor 1=2. Hence a vertex v can be dominated by a neighbour of v or by a number of vertices that are not too far from v. In this paper, we study the vulnerability of interconnection networks to the in uence of individual vertices, using a graph-theoretic concept of exponential domination number as a measure of network robustness.

Keywords

Graph vulnerability, Network design and communication, Domination, Exponential domination number, Trees.