有根星的最优边容错

Optimally Edge-fault Tolerance of the Rooted Stars

给定一个（有向）图H，称（有向）图G为关于H的k-边容错图，记为k－EHT（H）图，若从G中移去任何k条边所得的每个图都含有生成子图同构于H。G称为k－EFT（H）优图，若在所有k－EFT（H）图中，G的边数最小。G称为k－EFT（H）极图，若在所有k—EFT（H）代图中，G的点的最大度△（G）最小。设Sn表示有根星，对于每个n和k，本文表征了k-EFT（Sn）优图和极图。

Given a （directed） graph H, a （directed） graph G is a k-edge fault-tolerantgraph with respect to H, denoted k-EFT（H） graph, if G contains a spanning subgraph isomorphic to H after the removal of any k edges from G. G is an optimally k-EFT（I-I） graph if G contains the fewest edges among all k-EFT（H） graphs. G is an extremal k-EFT（FI） graph if the maximum degree of nodes of G is the smallest among all optimally k-EFT（H） graphs. Let Sn denote the rooted star with the out-degree of the root being n-1. A characterization of optimally or extremal k-EFT（Sn）graphs is obtained for all n and k in this paper.