Reconstruction Dans Les Graphes Orient? Et Color? Et Autres Probl?es

Stanley propose en 1981 un nouveau probl?me de reconstruction pour les graphes non-orient?s. Switcher en un sommet consiste ? remplacer toutes les ar?tes incidentes ? ce sommet par des non-ar?tes et vice-versa. Dans la premi?re partie nous pr?senterons de nouveaux probl?mes de reconstruction qui s'inspirent de, et g?n?ralisent, celui de Stanley, ainsi qu'une m?thode qui permet d'?tablir des r?sultats similaires ? ceux obtenus par Stanley, Ellingham et Royle, et Krasikov et Roditty dans le cas du probl?me de Stanley, en particulier un Lemme "? la Kelly." Dans la seconde partie nous pr?sentons la conjecture de Hahn et Jackson, qui s'ins?re dans le cadre de l'?tude des relations entre stables et chemins dans les graphes orient?s. Hahn et Jackson conjecturent que pour tout entier naturel k, il existe un graphe de stabilit? k tel que quelques soient les k-1 chemins que l'on supprime (avec leurs sommets) du graphe, la cardinalit? du graphe obtenu reste k. Cette conjecture est aussi forte que possible. Nous construisons explicitement une famille infinie de tels graphes, pour tout k de la forme 2 n.3 m, o? n et m sont deux entiers naturels.

Author: Mercier-F

Publisher: Omniscriptum

Publication Date: Feb 28, 2018

Number of Pages: 180 pages

Binding: Paperback or Softback

ISBN-10: 6131564329

ISBN-13: 9786131564321