Restricted Edge Connectivity And Hamiltonian Property Of Graphs

Graphs are often as models for the multiprocessor interconnection networks. There-fore, the performance of networks can be measured by the properties and parameters of graphs. One fundamental consideration in designing or selecting the network for a system is reliability (fault-tolerance). The edge connectivity λ(G) is one important feature deter-mining reliability and fault-tolerance of the network. In general, the larger the λ(G) is, the more reliable the network is. However, this parameter has an obvious deficiency, that is, it tacitly assumes that any set of elements (edges and/or vertices) can potentially fail at the same time, which happens almost impossible in the practical applications of networks. To compensate for this shortcoming, Fabrega and Fiol proposed the more general concept of κ-restricted edge connectivity.For interconnection networks, the problem of simulating one network by another is modelled as a network embedding problem. The graph embedding is a technique that maps a guest graph into a host graph. Many applications, such as architecture simulations, processor allocations, and VLSI chip designs, can be modeled as graph embeddings.This paper mainly investigates κ-restricted edge connectivity and Hamiltonian prop-erty of graphs. This thesis consists of five chapters. In Chapter 1, after a short introduc-tion to the used basic notation and terminology on graphs, a survey on the application backgrounds and the research advances of κ-restricted edge connectivity and Hamiltonian property of graphs are given. Finally, the main results acquired in this thesis are listed.The κ-restricted edge connectivity, was proposed by generalizing the edge connectiv-ity, is more refined network reliability indices. When k=2,2-restricted edge connectivity is often referred to as the restricted edge connectivity. In 2012, Holtkamp et al. gave the lower bound on the cardinality of the A2-fragments of a triangle-free graph, which is not maximally restricted edge connected, and the lower bound on the cardinality of the λκ-fragments of a 3-clique-free graph, which is not maximally κ-restricted edge connected. Moreover, sufficient conditions for maximally restricted edge connected and triangle-free graphs, and maximally κ-restricted edge connected and 3-clique-free graphs were showed. In Chapter 2, we investigate the maximally κ-restricted edge connectivity of (p+1)-clique-free graphs and graphs with girth g. First, the lower bound on the cardinality of the λκ-fragments of a (p+1)-clique-free graph, which is not maximally κ-restricted edge connected, is given. Next, we give the lower bound on the cardinality of the λκ-fragments of a non maximally κ-restricted edge connected graph with girth g. Finally, sufficient conditions for graphs to be maximally κ-restricted edge connected are proposed.In recent years, there are a lot of studies on maximally κ-restricted edge connected graphs for k=2,3, while the studies for general κ are relatively less. The general rules for general κ need to be explored further. In 2004, Hellwig and Volkmann proved that if |N(u) ∩ N(v)|≥ 2 for all pairs u, v of nonadjacent vertices of λ’-connected graph G, and for each triangle T there exists at least one vertex v ∈ V(T) such that d(v)≥ [(v(G)/2]+1, then G is maximally restricted edge connected. In Chapter 3, we investigate maximally κ-restricted edge connected graphs and supper κ-restricted edge connected graphs. First, we give a sufficient condition for graphs to be maximally κ-restricted edge connected, which extends the above result. Next, we show that if d(u)+d{v)≥ u(G)+2κ-4 for all pairs u, v of nonadjacent vertices and G is not in a special class of graphs, then G is maximally κ-restricted edge connected. Finally, a degree condition for a graph to be supper κ-restricted edge connected is given.The κ-isoperimetric edge connectivity, which is closely related to the concept of κ-restricted edge connectivity, is a crucial index to evaluate the reliability of interconnection networks. In 2009, Wang et al. showed that, for a graph G with order at least 2κ, if |N(x) ∩ N(y)|≥ 2κ-1 for all pairs x,y of nonadjacent vertices, then G is maximally κ-isoperimetric edge connected. Chapter 4 focuses on the neighborhood conditions for a graph to be maximally κ-isoperimetric edge connected. First, we show that there exists a (κ-1)-path in a subgraph of κ-isoperimetric edge connected graph G, which is induced by a γκ-fragment of G. Next, we give a neighborhood condition for a graph to be maximally isoperimetric edge connected, which improve the above result. Finally, we study the maximally κ-isoperimetric edge connectivity of graph with diameter 2.A Hamiltonian cycle of a graph G is a cycle passing through all vertices of G exactly once. Hamiltonian cycle embedding in graph is a hot topic in the field of graph theory. In chapter 5, we investigate Hamiltonian cycle embeddings in graphs with diameter 2. First, we introduce related concepts and results. Secondly, we show that if |N(u)∩N(v)|≥[v/2]-1 for all pairs u, v of nonadjacent vertices of graph G with order at least 3, and G is not in a special class of graphs, then G is a Hamiltonian graph.