EXPONENTIAL DOMINATION OF TREE RELATED GRAPHS

A. Aytaç, B. A. Atakul

[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 in uence on, or dominate, all vertices in its immediate neighbourhood, in some real world situations, this can be change. The vertex can also in uence all vertices within a given distance. This situation is characterized by distance domination. The in uence of the vertex in the graph doesn't extend beyond its neighbourhood and even this in uence 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, Ex- ponential domination number, Trees.