Graphs Orientations : structures and algorithms
Durand de Gevigney, Olivier
HAL, NNT: 2013GRENM027 / Harvested from HAL
Orienter un graphe c'est remplacer chaque arête par un arc de mêmes extrémités. On s'intéresse à la connexité du graphe orienté ainsi obtenu. L'orientation avec des contraintes d'arc-connexité est maintenant comprise en profondeur mais très peu de résultats sont connus en terme de sommet-connexité. La conjecture de Thomassen avance que les graphes suffisament sommet-connexes ont une orientation k-sommet-connexe. De plus, la conjecture de Frank propose une caractérisation des graphes qui admettent une telle orientation. Les résultats de cette thèse s'articulent autour des notions d'orientation, de packing, de connexité et de matroïde. D'abord, nous infirmons une conjecture de Recski sur la décomposition d'un graphe en arbres ayant des orientations avec degrés entrants prescrits. Nous prouvons également un nouveau résultat sur le packing d'arborescences enracinées avec contraintes de matroïdes. Ceci généralise un résultat fondamental d'Edmonds. Enfin, nous démontrons un nouveau théorème de packing sur les bases des matroïdes de dénombrement qui nous permet d'améliorez le seul résultat connu sur la conjecture de Thomassen. D'autre part, nous donnons une construction et un théorème d'augmentation pour une famille de graphes liée à la conjecture de Frank. En conclusion, nous réfutons la conjecture de Frank et prouvons que, pour tout entier k >= 3, décider si un graphe a une orientation k-sommet-connexe est un problème NP-complet.
Publié le : 2013-10-18
Classification:  Matroid,  Packing,  Connectivity,  Orientation,  Graph,  Matroïde,  Connexité,  Graphe,  [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
@article{NNT: 2013GRENM027,
     author = {Durand de Gevigney, Olivier},
     title = {Graphs Orientations : structures and algorithms},
     journal = {HAL},
     volume = {2013},
     number = {0},
     year = {2013},
     language = {en},
     url = {http://dml.mathdoc.fr/item/NNT: 2013GRENM027}
}
Durand de Gevigney, Olivier. Graphs Orientations : structures and algorithms. HAL, Tome 2013 (2013) no. 0, . http://gdmltest.u-ga.fr/item/NNT:%202013GRENM027/