IJPAM: Volume 37, No. 4 (2007)

VULNERABILITY OF GENERALIZED
PETERSEN GRAPHS VIA INVARIANTS

Elgin Kiliç$^1$, Pinar Dundar$^2$
$^{1,2}$Department of Applied Mathematics and Computer Sciences
Faculty of Science
Egean University
Bornova, Izmir, 35100, TURKEY
$^1$e-mail: [email protected]
$^2$e-mail: [email protected]


Abstract.Effectiveness of a network decreases if some nodes or links of it break down any way. Thus, communication network must be constructed to be stable as possible, not only with respect to the initial disruption, but also with respect to the possible reconstruction of the network. The vulnerability value of a communications network shows the resistance of the network after the disruption of some nodes or connection links until the communication breakdown. In a network, as the number of nodes belonging to sub networks changes, the vulnerability of the network also changes and requires less vulnerability or greater degrees of stability. If a graph is considered as a modelling network, many graph parameters have been used to describe the vulnerability of communications network, including connectivity, integrity and tenacity. Several of these deal with two fundamental questions about the resulting graph. How many vertices can still communicate? How difficult is it to reconnect the graph? Vulnerability numbers of a graph measure its durability respect to break down. We consider the integrity and tenacity of generalized Petersen graphs and the relation with its invariant.

Received: March 17, 2007

AMS Subject Classification: 26A33

Key Words and Phrases: graph theory, combinatorial optimization, network connectivity, network stability, communication networks

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2007
Volume: 37
Issue: 4