The integrity of a cubic graph |
| |
Authors: | A. Vince |
| |
Affiliation: | Department of Mathematics, University of Florida, Gainesville, FL 32611-8105, USA |
| |
Abstract: | Integrity, a measure of network reliability, is defined aswhere G is a graph with vertex set V and m(G−S) denotes the order of the largest component of G−S. We prove an upper bound of the following form on the integrity of any cubic graph with n vertices:Moreover, there exist an infinite family of connected cubic graphs whose integrity satisfies a linear lower bound I(G)>βn for some constant β. We provide a value for β, but it is likely not best possible. To prove the upper bound we first solve the following extremal problem. What is the least number of vertices in a cubic graph whose removal results in an acyclic graph? The solution (with a few minor exceptions) is that n/3 vertices suffice and this is best possible. |
| |
Keywords: | Integrity Network reliability |
本文献已被 ScienceDirect 等数据库收录! |
|