Maximally connected graphs and digraphs

The graph theoretical parameter edge-connectivity equals the minimum number of edges, whose removal disconnects the graph. Analogously, the vertex-connectivity equals the minimum number of vertices, whose removal disconnects the graph. These parameters are maximal, if they are equal to the minimum degree of the graph. Further connectivity parameters are the restricted edge-connectivity, the local-edge-connectivity and the p-q-restricted edge(vertex)-connectivity. In this thesis, we mainly study sufficient conditions for these connectivity parameters to be maximal. In Chapter 2,3,4 and 6 we generalize some known results by Goldsmith and Entringer and by Dankelmann and Volkmann. Furthermore we give analogue results to Xu's theorem for bipartite graphs. In Chapter 5 and 8 we characterize the graphs, where the parameters p-q-restricted edge-connectivity and p-q-restricted vertex-connectivity exists. In Chapter 9 we study the relations between edge- and vertex-connectivity parameters.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2005

Author dc:creator

• Hellwig, Angelika

Contributors dc:contributor

• Volkmann, Lutz

• info:eu-repo/classification/ddc/510
• Zusammenhängender Graph
• Digraph
• Mathematik
• Graph Theory
• Connectivity
• Edge-connectivity

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-123823%22

OAI identifier oai:identifier

oai:publications.rwth-aachen.de:62244