IJPAM: Volume 55, No. 1 (2009)

ON COMPUTING THE VULNERABILITY OF
SOME GRAPHS AS AVERAGE

Vecdi Aytac$^1$, Zeynep Nihan Odabas$^2$
$^1$Department of Computer Engineering
Ege University
Bornova, Izmir, 35100, TURKEY
$^1$e-mail: [email protected]
$^2$Department of Mathematics
Ege University
Bornova, Izmir, 35100, TURKEY
e-mail: [email protected]


Abstract.We investigate the resistance of a communication network to disruption of operation after the failure of certain stations or communication links, we use several vulnerability measures. If we think of a graph as modeling a network, the average lower independence number of a graph is one measure of graph vulnerability. For a vertex $v$ of a graph $G=(V,E)$, the lower independence number $i_v(G)$ of $G$ relative to $v$ is the minimum cardinality of a maximal independent set of $G$ that contains $v$. The average lower independence number of $G$, denoted by $i_{av}(G)$, is the value $\frac{1}{\left\vert V(G)\right\vert}\sum_{v\in V(G)}i_v(G)$. In this paper, we define and examine this parameter and consider the average lower independence number of binomial trees and middle graphs of some special graphs.

Received: July 20, 2009

AMS Subject Classification: 05C99, 68R10, 05C40, 05C69 90C27, 90B18

Key Words and Phrases: vulnerability, connectivity, graph theory, middle graph, average lower independence number

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2009
Volume: 55
Issue: 1