New upper bounds for the integrity of cubic graphs

Abstract

Integrity, a measure of network to reliability, is defined as

where G is a graph with vertex set V, and m(G − S) denotes the order of the largest component of G − S. Let V = n. It is known that (n/3) + O(√n) is a general upper bound for the integrity of any cubic graph. In this article, several theorems are shown that improve this general upper bound. For some families of cubic graphs, an upper bound for the integrity of (n/4) + O(√n) can be established using these theorems.

Keywords:

• Integrity
• Cubic Graph
• Cage Graph

Acknowledgement

C. Ernst was partially supported by NSF Grant #DMS-0310562.