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)
2017-12-26 - Article/Dans un journal avec peer-review - Anglais - 6 page(s) (Soumise)

Devillez Gauvain , Hauweele Pierre , Mélot Hadrien , "About a conjecture of Zhang, Liu and Zhou on the eccentric connectivity index" in Applied Mathematics-A Journal of Chinese Universities

  • 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) Let dn,m = for some integers n and m. In 2014, Zhang, 2 Liu and Zhou [3] published a conjecture characterising an unique graph that maximizes the eccentric connectivity index, among all connected graphs with given order n and size m such that dn,m ≥ 3. The authors gave also proofs for some special cases. In this paper we exhibit a family of graphs showing that extremal graphs are not unique when dn,m = 3. In this sense, these graphs form counter-examples to the conjecture. However, some experimental results obtained with a graph theoretical discovery system increase the belief that the conjecture may be true when dn,m > 3. Also, we characterize graphs maximizing eccentric connectivity index when dn,m ≤ 2. Indeed, these graphs were not covered by the conjecture.


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