Connectivity in graphs and digraphs : maximizing vertex-, edge- and arc-connectivity with an emphasis on local connectivity properties

Holtkamp, Andreas; Guo, Yubao (Thesis advisor)

Aachen / Shaker (2013) [Dissertation / PhD Thesis]

Page(s): IX, 144 S. : graph. Darst.


This thesis presents new results and ideas on connectivity in graphs and digraphs with a special emphasis on local connectivity properties. The research is divided into two parts, the first part dealing with graphs and the second one with digraphs. In Part I of this thesis we study some important connectivity parameters for graphs such as the vertex-, edge- and restricted edge-connectivity. Also, we introduce a local version of the restricted edge-connectivity. We present new results for all of these parameters to ensure (local) maximality/optimality in various classes of graphs. In Part II of this thesis we discuss connectivity parameters for digraphs. This includes the maximal local vertex-connectivity of regular and almost regular bipartite tournaments, and the vertex-connectivity of local tournaments. Furthermore, we study the restricted arc-connectivity and an according optimality criteria for tournaments and bipartite tournaments. In addition, we make a short excursion to examine the decycling problem for bipartite tournaments, i.e. determining the minimum number of arcs to be deleted from an arbitrary bipartite tournament to attain acyclicity. Finally, we study local optimality criteria for maximum network flows. We introduce a general concept to obtain (unique) locally optimal maximum network flows for arbitrary networks.


  • URN: urn:nbn:de:hbz:82-opus-47037