Maximally connected graphs and digraphs
type: CreativeWork
description: 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.
abstract: 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.
author: Hellwig, Angelika
language: eng
keywords: info:eu-repo/classification/ddc/510, Zusammenhängender Graph, Digraph, Mathematik, Graph Theory, Connectivity, Edge-connectivity
date published: 2005
date modified: 2026-07-30T19:43:19Z
provider: RWTH Aachen University
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: Publikationsserver der RWTH Aachen University