thesis

Problèmes extrémaux dans les graphes orientés

Defense date:

Jan. 1, 1987

Edit

Institution:

Paris 11

Disciplines:

Computer sciences

Authors:

Directors:

Abstract EN:

In this thesis we study sufficient conditions on the order, size, connectivity, independence number and degrees of the graphs and digraphs which imply the existence of cycles and paths. We determine conditions guaranteeing the existence of (1) cycles and paths of length greater (or smaller) than a given bound, (2) Hamiltonian cycles and paths, (3) cycle coverings for the vertices and (4) paths with specified end vertices. Bounds on the diameter of oriented graphs are also determined

Abstract FR:

Dans cette thèse nous avons étudié, pour des graphes orientés, des conditions suffisantes impliquant l’existence de cycles et chaînes sous les aspects suivants : cycles de longueur supérieure à une borne donnée, chaînes de longueur bornée inférieurement ou supérieurement, cycles et chaînes hamiltoniens, couverture des sommets par des cycles, existence de chaînes d’extrémités déterminées. Ces conditions concernent l’ordre, la taille, la connexité, la stabilité et les degrés du graphe.