Wiener Complexity versus the Eccentric Complexity

Martin Knor and Riste Škrekovski
Additional contact information
Martin Knor: Faculty of Civil Engineering, Slovak University of Technology in Bratislava, Radlinského 11, 81368 Bratislava, Slovakia
Riste Škrekovski: Faculty of Mathematics and Physics, University of Ljubljana, 1000 Ljubljana, Slovenia

Mathematics, 2020, vol. 9, issue 1, 1-9

Abstract: Let w G ( u ) be the sum of distances from u to all the other vertices of G . The Wiener complexity, C W ( G ) , is the number of different values of w G ( u ) in G , and the eccentric complexity, C ec ( G ) , is the number of different eccentricities in G . In this paper, we prove that for every integer c there are infinitely many graphs G such that C W ( G ) − C ec ( G ) = c . Moreover, we prove this statement using graphs with the smallest possible cyclomatic number. That is, if c ≥ 0 we prove this statement using trees, and if c < 0 we prove it using unicyclic graphs. Further, we prove that C ec ( G ) ≤ 2 C W ( G ) − 1 if G is a unicyclic graph. In our proofs we use that the function w G ( u ) is convex on paths consisting of bridges. This property also promptly implies the already known bound for trees C ec ( G ) ≤ C W ( G ) . Finally, we answer in positive an open question by finding infinitely many graphs G with diameter 3 such that C ec ( G ) < C W ( G ) .

Keywords: graph; diameter; wiener index; transmission; eccentricity (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/1/79/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/1/79/ (text/html)

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:gam:jmathe:v:9:y:2020:i:1:p:79-:d:473120

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().