Maximum eccentric connectivity index for graphs with given diameter

Hauweele, Pierre; Hertz, Alain; Mélot, Hadrien; Ries, Bernard; Devillez, Gauvain

doi:10.1016/j.dam.2019.04.031

Back

Journal article

Maximum eccentric connectivity index for graphs with given diameter

Hauweele, Pierre University of Mons, Belgium
Hertz, Alain Ecole Polytechnique de Montréal, Canada
Mélot, Hadrien University of Mons, Belgium
Ries, Bernard University of Fribourg, Switzerland
Devillez, Gauvain University of Mons, Belgium

2019

Published in:

Discrete Applied Mathematics. - 2019, vol. 268, p. 102-111

extremal graph theory

English The eccentricity of a vertex v in a graph G is the maximum distance between v and any other vertex of G. The diameter of a graph G is the maximum eccentricity of a vertex in G. The eccentric connectivity index of a connected graph is the sum over all vertices of the product between eccentricity and degree. Given two integers n and D with D ≤ n−1, we characterize those graphs which have the largest eccentric connectivity index among all connected graphs of order n and diameter D. As a corollary, we also characterize those graphs which have the largest eccentric connectivity index among all connected graphs of a given order n.

Faculty

Faculté des sciences économiques et sociales et du management

Department

Département d'informatique

Language