Higher Order Connectedness Of Graphs And Digraphs

With the rapid development of information networks, many theoreticalproblems come into focus, one of which is the reliability of the network, thatis, the ability of the network to function even when some vertices and/or edgesfail. The underlying topology of a network is often modeled as a graph or adigraph. So, some classical notations of graph theory, such as the connec-tivity and the edge(arc)-connectivity, is utilized to measure the reliability ofnetworks. For further study, many variations have been introduced, whichare known as higher connectedness, such as super-κ(super-λ), restricted edgeconnectivity and super-restricted edge connectivity, etc.In chapter 1, we introduce the background of our study and some nota-tions, and give definitions of line digraphs, Cartesian product and Lexico-graphic product of graphs, etc. Finally, we introduce studying contents andmain results in this paper. In chapter 2, we give the definitions of locallyrestricted-edge-connectivity and optimally local-restricted-edge-connectivityaccording to the definition of local-edge-connectivity of graphs, and then showthat some known su?cient conditions for a graph to be optimally restricted-edge-connected are also su?cient conditions for a graph to be optimally local-restricted-edge-connected. In chapter 3, we first study super-λCartesianproduct graphs. Then, we define the total transformation digraphs accordingto the definition of total transformation graphs, study the higher order con-nectivity of two kinds of total transformation digraphs and middle digraphs.Finally, we study some properties of iterated line digraph of complete bipartitedigraphs. In chapter 4, we define the double-super-connected digraphs, andcharacterize some special double-super-connected digraphs, including AbelianCayley digraphs, line digraphs, Cartesian product and Lexicographic productof digraphs.