一些图类的连通性

发布时间：2018-04-30 09:50

  本文选题：循环图 + 混合Cayley图　； 参考：《新疆大学》2017年博士论文

【摘要】：随着信息网络的迅速发展,网络的性能引起了人们的关注.信息网络的拓扑结构对网络的性能起着决定性的作用.在设计多处理器网络拓扑结构时,网络可靠性引起了人们的重视,网络可靠性即网络在它的某些部件(节点或者连接)发生故障时仍然能正常工作的能力.多处理器的互联网络通常被模型化为图,因此,图论中的一些经典概念(比如连通度和边连通度)就被用来研究网络的可靠性.为了进一步研究,人们提出了大量在网络优化设计中具有深刻背景的连通性概念,如超(边)连通性、圈点(边)连通性、限制性(边)连通性等等.本文主要研究混合Cayley图的圈边连通性,极小循环图的圈点连通性,笛卡尔乘积图的圈点连通性和限制性连通性,及半点传递有向图的连通度问题.第一章,我们介绍了研究背景和一些基本概念,术语以及符号,并对各类圈边连通性、圈点连通性、限制性连通性问题的研究现状进行了一定程度的回顾.第二章,我们研究了混合Cayley图的圈边连通性问题,并描述了圈边最优的充要条件.第三章,我们刻画了笛卡尔乘积图的圈点连通度和限制性连通度.对于笛卡尔乘积图,我们得到了圈点连通度的一个上界和下界,并对其3限制连通度和4限制连通度进行了研究,而对于κ≥ 5的限制性连通度,我们给出了两个猜想.第四章,我们研究了极小循环图的圈点连通度问题,并且给出对于任意的极小循环图X = C(Z_n,S)≥ 12),其圈点连通度k_c(X)=g(k-2),其中g是围长,κ(2)是正则度.第五章,我们对有向图的连通度进行了研究,并给出半点传递图的连通度等于该有向图的最小度。
[Abstract]:With the rapid development of information network, the performance of network has attracted people's attention. The topology of the information network plays a decisive role in the performance of the network. In the design of multi-processor network topology, network reliability has attracted much attention. Network reliability is the ability of network to work normally when some of its components (nodes or connections) fail. Multiprocessor networks are usually modeled as graphs, so some classical concepts in graph theory, such as connectivity and edge connectivity, are used to study the reliability of networks. For further study, a large number of connectedness concepts with profound background in network optimization design have been proposed, such as hyperconnectivity, cycle point connectivity, restricted connectivity and so on. In this paper, we study the cycle edge connectivity of mixed Cayley graphs, the cycle vertex connectivity of minimal cyclic graphs, the cycle point connectivity and restricted connectivity of Cartesian product graphs, and the connectivity of semipoint transitive digraphs. In the first chapter, we introduce the research background, some basic concepts, terms and symbols, and review the current research status of the problems of cycle edge connectivity, cycle point connectivity and restricted connectivity to a certain extent. In chapter 2, we study the cycle edge connectivity of mixed Cayley graphs and describe the necessary and sufficient conditions for cycle edge optimization. In chapter 3, we characterize the cycle point connectivity and restricted connectivity of Cartesian product graphs. For Cartesian product graphs, we obtain an upper bound and a lower bound of the connectivity of cycle points, and study its 3-restricted connectivity and 4-restricted connectivity. For the restricted connectivity of 魏 鈮，

本文编号：1824073