Nouveaux résultats sur les arbres, forêts et forêts linéaires maximum ainsi que sur la distance moyenne dans un graphe.

Cette thèse s'inscrit dans le domaine de la recherche scientifique assistée par l'ordinateur. Ce domaine est en pleine expansion depuis quelques années grâce aux récents développements des systèmes informatiques. En théorie des graphes plusieurs systèmes ont été développés afin de générer de nouvelles conjectures entre les différents invariants d'un graphe. Nous citons par exemple les systèmes AutoGraphiX, Graffiti et GraPHedron. Après un premier chapitre consacré à l'introduction, nous proposons dans le deuxième chapitre une revue de littérature sur les théorèmes connus ainsi que les conjectures qui bornent inférieurement ou supérieurement des invariants de graphe. Notre intérêt porte essentiellement sur la cardinalité des sous-graphes induits par un bistable, une forêt, une forêt linéaire et un arbre. Rappelons que ces problèmes sont NP-complets. Fajtlowicz a posé, respectivement pendant les années 1986 et 1992, les conjectures suivantes (générées par Graffiti et listées, parmi plusieurs, dans le document Written on the Wall): μ(G) ≤ α(G) (WoW 2) et μ(G) ≤ α2(G)/2 (WoW 747). Où μ(G) dénote la distance moyenne d'un graphe connexe, α(G) le nombre de stabilité et α2(G) la cardinalité du plus grand sous-graphe biparti induit. Il est clair que la deuxième conjecture est plus forte que la première, qui a été prouvée par Chung. Une autre preuve de la première conjecture a été proposée par Dankelmann, qui a aussi donné une description du graphe G qui maximise la distance moyenne pour un ordre donné et une valeur de α(G) donnée.