Sufficient conditions for existence of long cycles in graphs

Abstract

The aim of this thesis is to present sufficient conditions for existence of long cycles in simple graphs and in directed graphs, that is, cycles which pass through more than half of the vertices in a given graph. Namely, we want to find the minimal size of a given graph G guaranteeing that a cycle of prescribed length is contained in G. Optionally we consider a modification of this condition by adding a bound on the minimal degree of G. We investigate this problem for simple graphs, particularly bipartite, and also for digraphs, where all possible orientations of a cycle of given length are considered. Tematem rozprawy doktorskiej jest poszukiwanie warunków wystarczających na istnienie długich cykli w grafach, czyli cykli przechodzących przez ponad połowę wierzchołków w danym grafie. Celem jest określenie minimalnego rozmiaru grafu zapewniającego zawieranie się cyklu danej długości, ewentualnie określenie tego rozmiaru jednocześnie z minimalnym stopniem grafu. Problem jest rozważany dla grafów prostych, w szczególności dwudzielnych, jak i dla grafów skierowanych (tam interesujące są cykle o dowolnej orientacji). Rozdziały 1 i 2 rozprawy to streszczenia pracy, odpowiednio w językach polskim i francuskim. Rozdział 3 jest rozdziałem wstępnym. W rozdziale 4 prezentujemy podstawowe definicje i rezultaty istniejące w literaturze, związane z tematem tej rozprawy. W podrozdziale 4.1 prezentujemy podstawowe pojęcia i oznaczenia używane w pracy. W podrozdziale 4.2 podajemy listę wybranych warunków nahamiltonowskość jak i pancykliczność. Przedstawiamy także pojęcie domknięcia Bondy'ego-Chvatala. Prezentujemy również dwa twierdzenia Woodalla (twierdzenia 4.2.9 i 4.2.11) o długich cyklach w grafach prostych, które były inspiracją dla autora tej rozprawy. W podrozdziale 4.3 cytujemy różne warunki wystarczające nahamiltonowskośći pancykliczność digrafów, które są analogonami wyników przedstawionych w poprzednim podrozdziale. Podajemy także wyniki Heydemann, Sotteau i Thomassena, oraz Wojdy, dotyczące wszystkich orientacji cykli hamiltonowskich w digrafach. Na koniec prezentujemy historię pojęcia orientacji cyklu. W rozdziale 5 rozważamy problem długich cykli w grafach dwudzielnych. W podrozdziale 5.1 prezentujemy różne znane warunki wystarczające na hamiltonowskość jak i bipancykliczność takich grafów. Wyniki te są odpowiednikami rezultatów przedstawionych w podrozdziale 4.2.W szczególności przedstawiamy pojęcie bidomknięcia, bardzo ważnego narzędzia używanego w dowodzie głównego rezultatu podrozdziału 5.3. W podrozdziale 5.2 podajemy warunek wystarczający na rozmiar grafu dwudzielnego gwarantujący istnienie cyklu długiego (twierdzenie 5.2.1). Wynik ten jest podany wraz z dowodem. Dyskutujemy także, jak ten rezultat można by poprawić. W podrozdziale 5.3 rozważamy pewną modyfikację kryterium zaprezentowanego w poprzednim podrozdziale, tak zwany warunek typu Erdosa dla długich cykli w grafach dwudzielnych zrównoważonych. Przedstawiamy pewną hipotezę, a następnie dowodzimy ją dla specjalnego przypadku (twierdzenie 5.3.3). Rozdział 6 jest poświęcony problemowi długich cykli w grafach skierowanych. W podrozdziale 6.1 uogólniamy wynik Wojdy przedstawiony w podrozdziale4.3. Najpierw dowodzimy twierdzenie o cyklach symetrycznych i prawie symetrycznych w digrafach (twierdzenie 6.1.1). Następnie otrzymujemy wniosek o wszystkich orientacjach długich cykli w digrafach (wniosek 6.1.6). Na koniec porównujemy ostatni wynik z twierdzeniem Haggkvista i Thomassena o silnych orientacjach cykli w digrafach.W podrozdziale 6.2, zajmujemy się cyklami w digrafach dwudzielnych. Dowodzimy (używając twierdzenia 5.2.1) twierdzenie o cyklach symetrycznych i prawie symetrycznych(twierdzenie 6.2.4), a także o wszystkich orientacjach cykli w grafach dwudzielnych(wniosek 6.2.5). Są one odpowiednikami rezultatów dowiedzionych w poprzednim podrozdziale.