On the relation between Wiener index and eccentricity of a graph

Hamid Darabi (), Yaser Alizadeh (), Sandi Klavžar () and Kinkar Chandra Das ()
Additional contact information
Hamid Darabi: Esfarayen University of Technology
Yaser Alizadeh: Hakim Sabzevari University
Sandi Klavžar: University of Ljubljana
Kinkar Chandra Das: Sungkyunkwan University

Journal of Combinatorial Optimization, 2021, vol. 41, issue 4, No 3, 817-829

Abstract: Abstract The relation between the Wiener index W(G) and the eccentricity $$\varepsilon (G)$$ ε ( G ) of a graph G is studied. Lower and upper bounds on W(G) in terms of $$\varepsilon (G)$$ ε ( G ) are proved and extremal graphs characterized. A Nordhaus–Gaddum type result on W(G) involving $$\varepsilon (G)$$ ε ( G ) is given. A sharp upper bound on the Wiener index of a tree in terms of its eccentricity is proved. It is shown that in the class of trees of the same order, the difference $$W(T) - \varepsilon (T)$$ W ( T ) - ε ( T ) is minimized on caterpillars. An exact formula for $$W(T) - \varepsilon (T)$$ W ( T ) - ε ( T ) in terms of the radius of a tree T is obtained. A lower bound on the eccentricity of a tree in terms of its radius is also given. Two conjectures are proposed. The first asserts that the difference $$W(G) - \varepsilon (G)$$ W ( G ) - ε ( G ) does not increase after contracting an edge of G. The second conjecture asserts that the difference between the Wiener index of a graph and its eccentricity is largest on paths.

Keywords: Wiener index; Eccentricity; Eccentric connectivity; Tree; Extremal graph (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00724-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:41:y:2021:i:4:d:10.1007_s10878-021-00724-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00724-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().