DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2017-08-23 - Colloque/Présentation - communication orale - Anglais - 34 page(s)

Hauweele Pierre , Devillez Gauvain , Mélot Hadrien , "PHOEG Helps Obtaining Extremal Graphs" in Computers in Scientific Discovery 8, Mons, Belgium, 2017

  • Codes CREF : Mathématiques (DI1100), Théorie des graphes (DI1146), Recherche opérationnelle (DI1150), Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Algorithmique (S825)
  • Instituts UMONS : Institut de Recherche en Technologies de l’Information et Sciences de l’Informatique (InforTech), Institut de Recherche sur les Systèmes Complexes (Complexys)
  • Centres UMONS : Modélisation mathématique et informatique (CREMMI)
Texte intégral :

Abstract(s) :

(Anglais) Extremal graph theory aims to determine bounds for graph invariants as well as the graphs that attain those bounds. For example, one can study the eccentric connectivity index, ECI, a discriminating topological descriptor in biochemistry. The eccentric connectivity index of a given simple, undirected, connected, graph G, is defined as the sum (among all vertices) of the product of the degree and the eccentricity of each vertex. Some invariants (including ECI) may be hard to compute for a human and it might be difficult for one to develop intuitions about how they meld with graph structure. There is thus a need for tools to help researchers explore the intricacies of these invariants. This talk will present some aspects of the PHOEG system, an ecosystem of tools we are currently developing to help us with our research in Extremal Graph Theory. We will focus on the feature of querying a "big" database of graphs in order to check conjectures or infer new ones. It can be used to quickly confirm/infirm/obtain a conjecture on the problem of maximizing ECI under the constraints of fixing the graphs order and size, as well as quickly lighten or kill ideas in the process of seeking a proof for it.

Mots-clés :
  • (Anglais) Graph Theory
  • (Anglais) Database