摘要
一个图G中所含的三结点连通导出子图的个数记为S_3(G),它在网络可靠性中起着重要作用。在同点数同边数图类中具有最大S_3(G)的图称为3-优图,它所代表的网络是某种意义下的最可靠网络。3-优图的补图为3-最小图,而一个图称为3-极小图,如果在其上作任何一边的改变都不会减少其三结点连通导出子图的个数。本文提出一个构造算法,由该算法可以得到至今为止所知的所有的3-最小图,而且该算法所得的图都是3-极小图,因此猜想该算法所得的图是3-最小图。
The number of 3-nodes connected induced subgraphs S3(G) in a graph G plays a important role in the reliability of a network. The 3-optimal graph G is a graph that any graph G' with same numbers of edges and nodes subject to S(G')≤ S3(G), the 3-minimum graph is the complement of a 3-optimal graph, and the 3-minimal graph G is a graph that change any one edge of G do not decrease S3(G). In this paper, a construct algorithm is presented. It is conjectured that the graphs constructed by this algorithm are 3-minimum graphs, since all the 3-minimum graphs available can be obtained by this algorithm and all graphs constructed by this algorithm are 3-minimal graphs.
出处
《漳州师范学院学报（自然科学版）》
2003年第3期1-5,共5页
Journal of ZhangZhou Teachers College（Natural Science)
基金
福建省教委科技计划项目资助(JA00235)
