Connectivity in graphs and digraphs. Maximizing vertex-, edge- and arc-connectivity with an emphasis on local connectivity properties (Q2847903)

After a very nice introduction with a good overview of concepts of connectivity in graphs and digraphs together with algorithmic and complexity considerations, Part I of this thesis studies connectivity parameters of graphs and Part II deals with digraphs. A graph is maximally connected if its connectivity equals the minimum degree. It is maximally local (edge) connected if for any pair of vertices \(u\) and \(v\) the number of (edge) disjoint \(u\)-\(v\) paths is equal to \(\min\{d(u), d(v)\}\). \(k\)-restricted connectivity only considers cut-sets after whose deletion all components are of order at least \(k\). Degree conditions are provided to obtain maximum (local) connectivity in graphs with bounded clique number, \(p\)-partite graphs, diamond-free graphs, \(p\)-diamond-free graphs, \(K_{2,p}\)-free graphs and \(C_4\)-free graphs.NEWLINENEWLINENEWLINE Examples are given to show that the conditions are sharp. For a diamond-free graph \(G\) of order \(n \leq 4 \delta \), where \(\delta \) denotes the minimum degree of a vertex in \(G\), it is shown that \(G\) is maximally local-edge connected. Again, examples are provided to show the sharpness of the degree condition. Moreover, \(k\)-restricted edge connectivity and optimality is studied with particular results for \(k = 2, 3\). The main results of Part II are concerning the vertex-connectivity and local optimality of regular and almost regular bipartite tournaments and degree conditions and regularity criteria to insure optimality for restricted arc-connectivity. The maximum decycling index of a \(6 \times 6\) bipartite tournament is computed. Finally, local connectivity properties are used to optimize network flow, by introducing the new concept of maximum local flow. The work ends with some open problems and conjectures and is accompanied by a comprehensive bibliography.