The Connectivity And Super Connectivity Of Graphs

In this thesis, all graphs considered are simple, and a digraph may have loops but doesnot have multiple arcs (arcs with the same head and tail). A network can be modelled as agraph or a digraph. The classical measure of the reliability is the connectivity and the edgeconnectivity. For further study, many variations have been introduced, which are known ashigher order connectedness, such as super-connectivity, hyper-connectivity, super-λ, super-mixed-connectivity, and restricted edge connectivity, etc. This thesis studies higher orderconnectedness of graphs.The thesis is divided into three chapters. In Chapter 1, we introduce brie?y the backgroundof parameters about the reliability, and some terminologies. Chapter 2 studies two specialgraphs, In Section 2.2, we give some su?cient conditions for a dotgraph to be super-κ,super-λ, andλ-optimal. In Section 2.3, we prove that the reversal Cayley graphs are super-connected and hyper-connected ; and we also give a bound of the diameter of the graphs;finally, we show that the graphs are hamiltonian. Chapter 3 considers line graphs and linedigraphs. In Section 3.2, we prove that the line graph L(G) of a super-λgraph G is super-mixed-connected unless G belongs to a well characterized class of graphs. As a corollary,the line graph of every super-λgraph G with minimum degreeδ(G)≥3 is super-mixed-connected. In Section 3.3, we show that if a digraph D is super-arc-connected withδ(D)≥3,then Ln(D) is super-mixed-connected for any positive integer n. As a consequence, K(d,n)is super-mixed-connected for d = 2, and B(d,n) is always super-mixed-connected.