摘要
给定n≥2阶的连通图Go，n＋m阶图G称为关于Go是最优m-容错扩张，如果对于G的结点集的每个m-子集V，存在G—V的生成子图同构于Go，并旦G有尽可能少的边。设Go的补图的每个分支是非平凡的星或Ks，本文给出关于Go的全部最优m-容错扩张。
Given a connected graph Go of order n≥2,a graph G of order n＋m is called an optimal m-fault-tolerant extension witn respect to Go if for every m-subset V or the set of nodes of G, there exists a spanning subgraph of G-V which is isomorphic to Go and G has sa few edges as possible. Suppose that each component of the complement of Go is either a nontrivial star or triangle, all optimal m-faulttolerant extensions with respect to Go are presented in the paper.
基金
福建省教委1991年科研资助课题.
关键词
容错网络
网络的容错扩张
Fault- tolerant network, Fault-tolerant extension of a network
