环叶图的g-分量边连通度

The g-Component Edge Connectivity of Cycle-Leaf Graphs

摘要: 为了更好地评估多处理器互连网络在链路故障下的可靠性和容错能力，本文研究$g$ -分量边连通度，记为$c{\lambda }_g\left(G\right)$ ，它定义为使图$G$ 产生至少$g$ 个连通分量所需删除的最少边数。我们考虑环叶图，记为$\mathcal{C}ℒ\left(T;k_1,\cdots ,k_l\right)$ ，该图通过在树$T$ 的每个叶子顶点处与圈的一个顶点粘合而得到。首先，本文确定了轮图的$g$ -分量边连通度。随后给出了环叶图在$2\le g\le n\left(G\right)$ 范围内$g$ -分量边连通度的精确值。在此基础上，我们进一步研究环叶图的$g$ -分量边连通度序列，证明其相邻两项之差只能为1或2，并刻画了差为2的情况。最后证明，该序列能够唯一确定底层树的顶点数、附加圈的个数以及按非增次序排列的圈长序列。

Abstract: To better evaluate the reliability and fault tolerance of multiprocessor interconnection networks under link failures, we study the $g$ -component edge connectivity of a graph $G$ , denoted by $c{\lambda }_g\left(G\right)$ , which is defined as the minimum number of edges whose removal results in at least $g$ connected components. We consider a class of graphs called cycle-leaf graphs, denoted by $\mathcal{C}ℒ\left(T;k_1,\cdots ,k_l\right)$ , which are obtained by attaching a cycle to each leaf of a tree $T$ . First, we determine the $g$ -component edge connectivity of wheel graphs. Then, we obtain the exact value of the $g$ -component edge connectivity of cycle-leaf graphs for $2\le g\le n\left(G\right)$ . Based on this result, we further investigate the $g$ -component edge connectivity sequence of cycle-leaf graphs and prove that the difference between any two consecutive terms is either 1 or 2, with a characterization of the cases in which the difference is 2. Finally, we show that this sequence uniquely determines the order of the underlying tree, the number of attached cycles, and the sequence of cycle lengths arranged in non-increasing order.