On Uniformly Most Reliable Complete Multi-partite Graphs And Cyclic Vertex Connectivity Of Star Graphs

With the rapid development of information networks, many theoretical problemscome into focus, one of which is the reliability of the network, that is, the ability of thenetwork to function even when some vertices or edges fail. The underlying topology ofa network is often modeled as a graph or a digraph. So, some classical parameters ingraph theory, such as the connectivity and the edge-connectivity, are utilized to measurethe reliability of networks. But such parameters greatly underestimate the resilience oflarge scale networks. To overcome this problem, many variations on connectivity havebeen introduced, which are known as higher order connectedness, such as restricted edgeconnectivity, super-restricted edge connectivity, cyclic edge connectivity, cyclic vertexconnectivity etc. In this thesis, we mainly study the uniformly most reliable completemulti-partite graphs and the cyclic vertex connectivity of star graphs.This thesis is divided into three chapters. In Chapter 1, we state the background ofour study, and introduce some notation. Closely related works are surveyed in Chapter1. In Chapter 2, we prove that the complete k-parte graphs K(b,(b + 1)k?3,(b + 2)2) areuniformly most reliable in their classes. We also show that K(bh,(b + 1)k?h?1,(b + 2)1)is not uniformly most reliable in its class for any h≥2. In Chapter 3, we show thatfor any integer n≥4, the n-dimensional star graph SGn has cyclic vertex connectivityκc(SGn) = 6(n ? 3).