Linear inequalities among graph invariants: using GraPHedron to uncover optimal relationships

Julie Christophe (juchristulb.ac.be)
Sophie Dewez (sdewezulb.ac.be)
Jean-Paul Doignon (doignonulb.ac.be)
Sourour Elloumi (elloumicnam.fr)
Gilles Fasbender (gfasbendulb.ac.be)
Philippe Grégoire (pgregoirsmg.ulb.ac.be)
David Huygens (dhuygenssmg.ulb.ac.be)
Martine Labbé (mlabbeulb.ac.be)
Hadrien Mélot (hadrien.melotumh.ac.be)
Hande Yaman (hyamansmg.ulb.ac.be)

Abstract: Optimality of a linear inequality in finitely many graph invariants is defined through a geometric approach. For a fixed number of graph nodes, consider all the tuples of values taken by the invariants on a selected class of graphs. Then form the polytope which is the convex hull of all these tuples. By definition, the optimal linear inequalities correspond to the facets of this polytope. They are finite in number, are logically independent, and generate precisely all the linear inequalities valid on the class of graphs. The computer system GraPHedron, developed by some of the authors, is able to produce experimental data about such inequalities for a

Keywords: Graph invariants, polytope, optimal linear inequalities, GraPHedron

Category 1: Other Topics (Other )

Citation: Submitted in Augustus 2004

Download: [PDF]

Entry Submitted: 09/21/2004
Entry Accepted: 09/21/2004
Entry Last Modified: 09/21/2004

Modify/Update this entry