Connectivity, diameter, minimal degree, independence number and the eccentric distance sum of graphs

The eccentric distance sum (EDS) of a connected graph G is defined as ξd(G)=∑{u,v}⊆VG(εG(u)+εG(v))dG(u,v), where εG(⋅) is the eccentricity of the corresponding vertex and dG(u,v) is the distance between u and v in G. In this paper, some extremal problems on the EDS of an n-vertex graph with respect...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2018-10, Vol.247, p.135-146
Main Authors: Chen, Shuya, Li, Shuchao, Wu, Yueyu, Sun, Lingli
Format: Article
Language:English
Subjects:
[formula omitted]-connected
Computational mathematics
Connectivity
Eccentric distance sum
Eccentricity
Geometry
Graph theory
Graphs
Independence number
Lower bounds
Minimum degree
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The eccentric distance sum (EDS) of a connected graph G is defined as ξd(G)=∑{u,v}⊆VG(εG(u)+εG(v))dG(u,v), where εG(⋅) is the eccentricity of the corresponding vertex and dG(u,v) is the distance between u and v in G. In this paper, some extremal problems on the EDS of an n-vertex graph with respect to other two graph parameters are studied. Firstly, k-connected (bipartite) graphs with given diameter having the minimum EDS are characterized. Secondly, sharp lower bound on the EDS of connected graphs with given connectivity and minimum degree is determined. Lastly sharp lower bound on the EDS of connected graphs with given connectivity and independence number is determined as well.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2018.03.057