Characterizations and constructions in graph connectivity

Date

2025-9-25

Author

Tekdaş, Arsen Berk

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

53
views

0
downloads

Cite This

This thesis surveys two constructive characterizations of uniformly 3-connected graphs, presents Ando's alternative proof of Tutte’s construction for 3-connected graphs, and introduces a construction for 4-connected graphs. Along the way, we also examine some properties of minimally k-connected graphs. Finally, we implement a random construction algorithm for 3-connected graphs based on Tutte's constructive characterization, along with two algorithms for 4-connected graphs and an algorithm for uniformly 3-connected graphs derived from the constructive characterizations of Slater, Ando and Göring et.al, respectively.

Subject Keywords

Connectivity, Minimal k-connectivity, Uniform k-connectivity, 3-connectivity, 4-connectivity

URI

https://hdl.handle.net/11511/116204

Collections

Graduate School of Natural and Applied Sciences, Thesis