用图来表示互连网络拓扑结构已被计算机和工程技术人员广泛运用.在本文中,"图"和"互连网络"不作区分.网络的可靠性通常用图的连通度来表示.外连通度是传统连通度的推广,更能准确的分析各种互连网络的可靠性.哈密尔顿性是设计网络时最基本的要求之一.网络故障不可避免,具有故障元素的哈密尔顿路和圈嵌入问题具有实际意义.诊断度是测量网络容错性的重要参数.本文主要研究图的外连通度,网络的容错哈密尔顿性以及故障诊断.本文的结构如下:第一章是引言部分,主要介绍图的条件连通度,网络容错哈密尔顿性以及故障诊断的研究背景.第二章,给出了本文所用到的图论的基本概念.第三章,研究了k-元立方体Qnk的外连通度.当n ≥ 3时,证明了 3-元n-立方体Qn3的3-外连通度是8n-12,其结果大概是传统连通度的4倍.当n ≥ 3和k≥4时,证明了k-元n立方体Qnk的3-外连通度是8n-9,此结果与k的取值无关.这一结论扩展了 Zhao等人关于Qn3的2-外连通度以及Hsieh等人关于Qnk的2-外连通度的结果.第四章,研究了平衡超立方体的容错哈密尔顿性.关于平衡超立方体的容错性,已知的结果大多都是只考虑故障点或者故障边.我们考虑同时具有故障点和故障边的容错性.首先证明了平衡超立方体具有故障点和故障边数目不超过2n-2并且故障点数目不超过n-1情况下的哈密尔顿圈的存在性.令Fv和Fe分别表示BHn(n≥2)中的故障点和故障边的集合.如果|Fe| + |Fv| ≤ 2n-2且|Fv|≤n-1,则BHn中存在一个无故障的长度为22n-2|Fv|的圈.其次证明了平衡超立方体在故障边数目不超过n-1的情况下具有强哈密尔顿交织性.设x和y是BHn中同一部中的任意两点.令Fe是一些故障边的集合.如果|Fe|≤n-1且n≥1,那么在BHn中存在一条无故障的长度为22n-2的从x到y路.也就是说,BHn是(n-1)-边容错强哈密尔顿交织的.第五章,主要研究网络的诊断,包括悲观诊断,条件诊断以及g-好邻诊断.第一节研究了 PMC模型下的悲观诊断.首先得到了 k-正则k-连通图类Gn在满足某些条件下的悲观诊断.作为应用,我们导出了交错群图AGn,交错群网络ANn,k-元n-立方体网络Qnk,星图Sn以及匹配组合网络MCN的悲观诊断.这些图类具有共同的特点,相邻两个点的最大公共邻点的个数小于等于2.其次,考虑了没有公共邻点个数限制的几类网络的悲观诊断,包括(n,k)-排列图An.k,(n,k)-星图Sn,k,平衡超立方体BHn,泡沫排序星图BSn,增广k-元n-立方体AQn,k以及数据中心网络Dk,n等.第二节研究数据中心网络Dk,n的条件诊断.通过分析Dk.n在至多删去n +4k-5个点后所得连通分支的情况,得到了Dk,在PMC模型和MM模型下的条件诊断分别是n + 4k-3 ≥ 2,n≥4)和n + 3k-3(k ≥ 2,n≥2).第三节研究g-好邻诊断.令tc(G)和tg(G)分别表示图G的条件诊断度和g-好邻诊断度.对于大多数的网络,1-好邻诊断度与条件诊断度并不相等.本节主要考虑平衡超立方体BHn,得到了 BHn的1,2-好邻诊断度.并证明了其1-好邻诊断度与条件诊断度相等.第六章,总结全文并提出一些待研究的问题.