Titre de la dissertation :Extremal properties of average-based and chemical graph invariants.

 Promoteur de thèse: Monsieur Hadrien Melot

Résumé de la dissertation : A graph is a mathematical structure used to model pairwise relationships between objects. Formally, a graph consists of a set of vertices together with a set of edges that connect certain pairs of vertices. Graphs provide a flexible and powerful language for representing networks in diverse contexts.

Extremal graph theory is a branch of graph theory that studies how constraints influence the structure of graphs. Typically, it asks questions of the following form: given a fixed property or forbidden configuration, what is the maximum or minimum possible value of a graph invariant? It can also focus on characterizing the graphs that maximize or minimize a given invariant under prescribed conditions.

In this thesis, we investigate extremal problems involving average-based invariants, that is, invariants defined as the average size of distinct configurations, substructures, or combinatorial patterns of a specific type in a graph. More specifically, we study the average number of non-equivalent colorings of a graph and the average size of maximal matchings in graphs.

We also present results in chemical graph theory, where graphs represent molecular structures: vertices correspond to atoms and edges to chemical bonds. Many molecular descriptors used in chemistry—such as degree-based topological indices—are relevant to physical, chemical, or biological properties of compounds. Our work starts with a study of the arithmetic-geometric index, a degree-based topological index, and ends in a complete polyhedral description of chemical graphs of maximum degree at most 3. More precisely, we characterize the feasible region of these graphs through the parameters m_ij​, which count edges between vertices of degrees i and j. This characterization allows us to systematically identify families of chemical graphs that are extremal with respect to degree-based topological indices.

In addition to the theoretical results, we developed PHOEG, an interactive web-based tool which assists researchers in extremal graph theory by exploring relationships between graph invariants and identifying extremal graphs using geometric and database-driven methods. It supports the formulation of conjectures and the investigation of bounds for graph invariants. In the same spirit, we developed ChemicHull, an online tool for extremal graph theory in mathematical chemistry that lists and allows the visualization of the 96 polytopes arising in the aforementioned polyhedral description. Users can filter these polytopes by assigning specific values to the number of vertices and/or the number of edges, or by using formulas involving these parameters.