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.

Abstract

There are many discovery systems in graph theory that have been designed to generate new conjectures and explore graphs. For instance the systems AutoGraphiX, Graffiti and GraPHedron. After the introduction, we present in the second chapter a survey on theorems and conjectures that give bounds on some graph invariants. We are concerned by the order of a largest induced subgraph (bipartite, forest, linear forest, tree). We recall that these problems are NP-hard. With the help of the Graffiti system, Fajtlowicz conjectured around 1992 [36] that the average distance between two vertices of a connected graph G is at most half the maximum order of an induced bipartite subgraph of G, denoted α2(G). We prove in the third chapter a strengthening of this conjecture by showing that the average distance between two vertices of a connected graph G is at most half the maximum order of an induced forest, denoted F(G). It is the main result of this thesis. Finally, we conjecture that the average distance between two vertices of a connected graph is at most half the maximum order of an induced linear forest (where a linear forest is a union of paths). Moreover, we characterize the graphs maximizing the average distance among all graphs G having a fixed number of vertices and a fixed value of F(G) or α2(G).