将互连网络中的每个处理器抽象成一个点,把处理器之间的信道抽象成两点之间的连线,那么一个互连网络就可以抽象成一个图,称之为互联网络拓扑结构,网络的拓扑结构决定着该网络的性能.由于互联网络的拓扑结构就是图,所以图论是设计和分析互连网络的最基本且强有力的数学工具.可嵌入性是衡量网络优劣的一个重要性能.由于用含有圈拓扑结构的图设计出来的网络通讯成本低,而且泛圈性和泛连通性也可以看成是图的哈密顿性研究的扩展,因此圈嵌入是一个重要问题.由于网络的节点和链接都可能发生故障,所以需要研究网络的容错性,这是评估网络性能时所考虑的主要因素之一交替群图作为计算机系统的一种互联网络拓扑结构,具有许多比超立方体和星图更好的性质,也符合网络设计高性能、低成本的原则要求.本文研究了交替群图等几类著名互联网络的容错圈嵌入、最大边连通、网络设计等问题,主要研究工作如下：(1)研究了交替群图的容错哈密顿性和容错哈密顿连通性.对于一个n-维交替群图AGn,证明了当n≥4时,AGn是(2n-6)-容错哈密顿和(2n-6)-容错泛圈的,并且是(2n-7)-容错哈密顿连通的.本文所给的结果关于交替群图的正则度是最优的,也是对以前J.-M.Chang等人所给结果的改进.(2)定义了匹配组合网络G=G(V1UV2,E1UE2UM),其中M是V1和V2之间的一个完全匹配.研究了G的限制连通度,G的直径的上下界与G1的直径、G2的直径和完全匹配M的关系,通过G1和G2的阶确定了几类特殊匹配组合网络G直径的上下界,最后讨论了G1和G2的泛圈性和泛连通性与G的泛圈性和泛连通性之间的关系.(3)用凸函数的性质和数论知识研究了连通图的倒数度的上界,给出了一个连通图是最大边连通的条件,为研究超连通或超边连通图提供了新的方法,通过例子说明所给结果用于判断一个连通图是否是最大边连通图是有效的.(4)线图方法、笛卡儿乘积方法和代数方法是互联网络设计常用的三种方法.本文用代数方法对任何含有最小元素的偏序集P,定义了其相关联零因子图G(P),证明了如果G(P)的色数X(G(P))和团数ω(G(R))是有限的,那么χ(G(P))=ω(G(P))=n+1,其中n是P的极小素理想的个数.