星网络的最优边容错图的结构

The Constructure of Optimal Edge Fault Tolerant Graphs of the Star Networks

若图G小去掉任何k条边后所得的图含有生成子图同构于G0，则称G关于G0；是k边容错图，记为k－EFT（G0）．若G是k－EFT（G0）图且过数尽可能小，则称G为最优k－EFT（G0）图．设Sn；表示n点星．若一个最优k-EFT（Sn）图的最大度尽可能小，则称为（k，n）一极图本文对于所有的k和n，表征了最优k－EFT(Sn）图和(k，n）一极圈的结构．

Let G and G, be graphs on n nodcs. G is k -edge fault tolerant with respect to Go, denoted by k -EFT(G0), if every graph obtained by removing any k edges from Gcontains a subgraph Go. G is an optimal k - EFT(G0) graph if G is a k - EFT(G0) graph with as few edges as possible. Let Sn denote tlie star on n nodes. A (k, n) - extremal graph is an optimal k - EFT(Sn ) graph whose maximam degree is as small as possible- In this paper the constructure or optimal k-EFT(Sn) graphs and of the (k, n) - extremal graphs is characterized for all k and n.