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)
2019-11-15 - Colloque/Présentation - communication orale - Anglais - page(s)

Devillez Gauvain , Hauweele Pierre , Hertz Alain, Mélot Hadrien , "Minimizing the eccentric connectivity index with fixed number of pending vertices" in 21st Journées Graphes et Algorithmes, Bruxelles, Belgique, 2019

  • 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 (noted eG (v)) as the maximal distance between v and any other vertex of G. The degree of a vertex (noted 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. [1]. X ECI(G) = dG (v) · eG (v). v∈V 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, then one too many pending vertex is made adjacent to one of the vertices covered by the matching. In this talk we determine which graphs with n vertices and p pending ver- tices have a minimum value of ECI for a given values n and p. We show that among these graphs, Gn,p is the graph minimizing ECI with the exception of some particular cases. Références [1] V. Sharma, R. Goswani, and A.K Madan. Eccentric Connectivity Index : A Novel Highly Discriminating Topological Descriptor for Structure Pro- perty and Structure Activity Studies. J. Chem. Inf. Comput. Sci., 37 :273 – 282, 1997.


Mots-clés :
  • (Anglais) extremal graph theory
  • (Anglais) graph theory
  • (Anglais) eccentric connectivity index
  • (Anglais) pendant vertices