<  Retour au portail Polytechnique Montréal

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

Rim Kilani

Thèse de doctorat (2010)

Document en libre accès dans PolyPublie
[img]
Affichage préliminaire
Libre accès au plein texte de ce document
Conditions d'utilisation: Tous droits réservés
Télécharger (736kB)
Afficher le résumé
Cacher le résumé

Résumé

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).

Département: Département de mathématiques et de génie industriel
Programme: Mathématiques de l'Ingénieur
Directeurs ou directrices: Alain Hertz, Pierre Hansen et Odile Marcotte
URL de PolyPublie: https://publications.polymtl.ca/461/
Université/École: École Polytechnique de Montréal
Date du dépôt: 25 févr. 2011 15:05
Dernière modification: 16 nov. 2022 14:27
Citer en APA 7: Kilani, R. (2010). Nouveaux résultats sur les arbres, forêts et forêts linéaires maximum ainsi que sur la distance moyenne dans un graphe. [Thèse de doctorat, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/461/

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Actions réservées au personnel

Afficher document Afficher document