Loading…
Degree Bounds for the Circumference of Graphs
Wumaier, Aierken
In dieser Dissertation werden neue Gradabschätzungen für den Kreisumfang c(G) von k-zusammenhängenden Graphen G mit 3 <= k <= 5 angegeben. Sei C ein längster Kreis in G und L(G-C) die Länge der längsten Wege in G-C :=G-V(C). Es ist bekannt, daß c(G) =|C| >= (k+1)delta-(k+1)(k-1) gilt, wenn L(G-C) >= k-1 und G ein (k+1)-zusammenhängende Graph ist. Die Ausnahmeklassen bzgl. dieser Abschätzungen für k-zusammenhängende Graphen werden im wesentlichen bestimmt. Für 3-zusammenhängende Graphen G werden die Ausnahmeklassen bzgl. der Abschätzung |C| >= 4delta-c bei L(G-C) >= 2 für 5 <= c <= 8 im wesentlichen bestimmt.
In this thesis we present degree bounds for the circumference c(G) of k-connected graphs G with 3 <= k <= 5. Let C be a longest cycle in a graph G and let L(G-C) be the length of a longest path in G-V(C). Let 2 >= k >= 5 and L(G-C) >= k-1. It is known that c(G)= |C| >= (k+1)delta-(k-1)(k+1), if G is (k+1)-connected and n = |G| >= (k+1)δ-k(k-1), if G is k-connected. The exceptional classes for these estimates when the connectivity is reduced by 1 are essentially determined. Moreover, for 3-connected graphs G, the exceptional classes for the estimates c(G) >= 4delta-c for 5 <= c <= 8 are essentially characterized.
