论文部分内容阅读
网络的可靠性是指当网络中某些链路或节点失效时，网络能继续进行通讯的能力。而图的连通性在网络可靠性研究中具有重大的理论和实际意义。1978年，Gunther和Hartnell[9]基于间谍网络提出了图的邻域连通度的概念，在邻域意义下考虑图的连通性。 设G=（V，E）为一个图，对于图G中的任意顶点u∈V，N(u)={v∈V|v与u相邻}表示顶点u的开邻域，N[u]＝N（u）∪{u}表示顶点u的闭邻域。对于一个顶点集U∈V，N(U)={v|v与U中的顶点相邻}，N[U]=N(U)∪U。如果G-N[U]得到的新图G(O)U或者为空，或者是完全图，或者不连通，我们就称U是G的一个点割策略。图G的所有点割策略中的最小基数称为G的点邻域连通度，记为κNB(G)。 类似地，对于图G中的边e∈E，N(e)={f∈E|f与e相邻}表示边e的开邻域，N[e]＝N(e)∪{e}表示边e的闭邻域。对于一个边集S∈E，N(S)={f|f与S中的边相邻}，N[S]=N(S)∪S。如果从图G中删去N[S]以及S中的边所关联的端点后得到的新图G(O)S或者为空，或者是平凡图，或者不连通，我们就称S所包含的边的集合为G的一个边割策略，图G的所有边割策略中的最小基数称为G的边邻域连通度，记作λNB(G)。 目前，国内外针对邻域连通度的研究成果并不多，在文献[5]中，作者给出了图的边邻域连通度的一些基本结论。文献[30]研究了图与线图的关系，得到了图的边邻域连通度与它的线图的点邻域连通度之间的关系。文献[26]给出了笛卡尔积图G×K2和Kn×K2的边邻域连通度。文献[21]则得到了折叠超立方体图FQn的边邻域连通度。由此可以看出，针对图的点邻域连通度的研究空间还很大，而且许多具体图类的邻域连通度结论也未知，这也正是我们的研究意义所在。 本论文所得出的结论包含以下几个方面:首先讨论了k-正则图G和K3的笛卡尔积图G×K3，n个K3的笛卡尔积图Gn的边邻域连通度，证明满足一定条件时有λNB（G×k3）=K+1，λNB(Gn)=n。此外，对一类特殊的Cayley图:交错群网络ANn=Cay(4，Ω)，其中An是={1，2，…，n}上全体偶置换构成的子群，Ω={(123)，(132)，(12)(3i):i＝4，…，n}。我们导出了它的点邻域连通度和边邻域连通度，证明了κNB(ANn)=n-1，λNB（ANn）=n-2。最后，基于由交换树生成的Cayley图Γn的概念和性质，研究了Γn的邻域连通性，证明了它的点邻域连通度和边邻域连通度分别为κNB(Γn)=n-1，λNB(Γn)=n-1，在此基础上又得到了关于星图Sn和泡形图Bn的邻域连通度的推论:κNB(Sn)=λNB(Sn)=n-1，κNB（Bn）=λNB（Bn）=n-1。