Maximally connected graphs and digraphs

Hellwig, Angelika; Volkmann, Lutz

doi:urn:nbn:de:hbz:82-20050846

Maximally connected graphs and digraphs

Hellwig, Angelika (Author)

2005

Verantwortlichkeitsangabevorgelegt von Angelika Hellwig

ImpressumAachen : Publikationsserver der RWTH Aachen University 2005

UmfangII, 105 S.

Aachen, Techn. Hochsch., Diss., 2005

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Volkmann, Lutz (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2005-04-27

Online
URN: urn:nbn:de:hbz:82-20050846
URL: https://publications.rwth-aachen.de/record/62244/files/Hellwig_Angelika.pdf

Einrichtungen

Fakultät für Mathematik, Informatik und Naturwissenschaften (100000)

Inhaltliche Beschreibung (Schlagwörter)
Zusammenhängender Graph (Genormte SW) ; Digraph (Genormte SW) ; Mathematik (frei) ; Graph Theory (frei) ; Connectivity (frei) ; Edge-connectivity (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Die graphentheoretischen Parameter Kantenzusammenhangszahl bzw. Eckenzusammenhangszahl entsprechen der kleinsten Anzahl von Kanten bzw. Ecken, deren Entfernung den Zusammenhang des Graphen zerstört. Diese Parameter sind maximal, wenn sie gleich dem minimalen Eckengrad des Graphen sind. Weitere Zusammenhangsparameter sind die bedingte Kantenzusammenhangszahl, die lokale Kantenzusammenhangszahl, die bedingte p-q-Kantenzusammenhangszahl und die p-q-Eckenzusammenhangszahl. In dieser Doktorarbeit werden hauptsächlich hinreichende Bedingungen für die Maximalität der verschiedenenen Zusammenhangsparameter angegeben. In den Kapiteln 2,3,4 und 6 werden bekannte Resultate von Goldsmith und Entringer, sowie Dankelmann und Volkmann verallgemeinert. In den Kapitel 5 und 8 werden die Graphen charakterisiert, für die die p-q-bedingte Kantenzusammenhangszahl bzw. Eckenzusammenhangszahl existiert. Im Kapitel 9 wird das Verhältnis der Kanten- und Eckenzusammenhangsparameter zueinander untersucht.

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.

Volltext:
PDF
(zusätzliche Dateien)