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

Recherche transversale
Rechercher
(titres de publication, de périodique et noms de colloque inclus)
2018-06-14 - Colloque/Présentation - communication orale - Anglais - 19 page(s)

Devillez Gauvain , "Minimizing the eccentric connectivity index with a fixed number of pending vertices" in 31th Conference of the European Chapter on Combinatorial Optimization, University of Fribourg, Fribourg, Switzerland, 2018

  • 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 (called ECI) and, given a number of nodes and pending vertices, search to minimize it. Given a connected graph G = (V, E), we define the eccentricity of a vertex v (eG(v)) as the maximal distance between v and any other vertex of G. The degree of a vertex (dG (v)) is the number of adjacent vertices and vertices with degree 1 are called pending. We define ECI as the sum for every vertex of the product between its degree and its eccentricity. This invariant was introduced by Sharma et al. We define the graph Gn,p as the graph with n vertices and p pending vertices obtained by taking a star with n vertices and adding a maximum matching between n−p−1 pending vertices. If n − p − 1 is odd, the one too many pending vertex is made adjacent to one of the vertices covered by the matching. In this talk we determine which graphs have a minimum value of ECI for a given number n of vertices and a given number p of pending vertices. We show that among these graphs, Gn,p is the graph minimizing ECI with the exception of some particular cases.


Mots-clés :
  • (Anglais) Graph theory