The integrity of a cubic graph
The integrity of a cubic graph
复制标题
DOI：
10.1016/j.dam.2003.07.002
复制
发表时间：
2004-05
期刊：
影响因子：
--
通讯作者：
A. Vince
中科院分区：
文献类型：
--
作者：
A. Vince
完整性是衡量网络可靠性的一种指标，定义为[公式：见文本]，其中G是顶点集V的图，m（G−S）表示G−S中最大分量的阶数。我们证明了任意有n个顶点的三次图的完整性的上界：[公式：见文]并且，存在一个无限族的连通三次图，其完整性满足某常数β的线性下界I(G)>βn。我们为β提供了一个值，但它可能不是最好的。为了证明上界，我们首先解决下面的极值问题。在一个三次图中，移除会得到一个无环图的最少顶点数是多少？解决方案（除了少数例外）是n/3个顶点就足够了，这是最好的选择。
Integrity, a measure of network reliability, is defined as [Formula: see text] where 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: [Formula: see text] 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.