Group for Research in Decision Analysis

PHOEG helps obtaining extremal graphs

Hadrien Mélot Université de Mons, Belgium

Extremal graph theory aims to determine bounds for graph invariants as well as the graphs that attain those bounds. Some invariants may be hard to compute and it might be difficult for a human 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. There already are attempts to reach that goal, e.g., Graph, GrInvIn, Graffiti, AutoGraphiX, Digenes, GraPHedron. However those tools do not fully meet our needs to obtain extremal graphs in an exact manner and to explore graph transformations. Being able to quickly make queries on graph invariants is also an interesting feature to quickly lighten or kill ideas in a research discussion, e.g., "which graphs are local minima for some transformation with respect to some invariant?" or "on which connected graphs are two invariants equal?".

In an attempt to answer such questions (and others), we are currently developing the Phoeg system, which can be viewed as a successor to GraPHedron. It uses a big database of graphs and works with the convex hull of the graphs as points in the invariants space in order to exactly obtain the extremal graphs (of small order) and infer optimal bounds on the invariants. This database also allows us to make queries on graphs. Phoeg goes one step further by helping in the process of designing a proof guided by successive applications of transformations from any graph to an extremal graph.


Free entrance.
Welcome to everyone!