Wiener complexity versus the eccentric complexity

Knor, Martin (avtor), Škrekovski, Riste (avtor)

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) ≤ 2C$_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).

• Jezik: Angleški jezik
• Ključne besede: graph, diameter, Wiener index, transmission, eccentricity
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2021
• Št. strani: 9 str.
• Številčenje: Vol. 9, iss. 1, art. 79
• PID: 20.500.12556/RUL-134930
• UDK: 519.17
• ISSN pri članku: 2227-7390
• DOI: 10.3390/math9010079
• COBISS.SI-ID: 46211331
• Datum objave v RUL: 11.02.2022

Gradivo je del revije

• Naslov: Mathematics
• Skrajšan naslov: Mathematics
• Založnik: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.
• Začetek licenciranja: 01.01.2021

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: graf, diameter, Winerjev indeks, transmisija, ekscentričnost