Subtree number versus Wiener index

Knor, Martin (avtor), Sedlar, Jelena (avtor), Škrekovski, Riste (avtor), Yang, Yu (avtor)

The subtree number $N(G)$ of a graph $G$ is defined as the number of non-empty subtrees of $G$. The Wiener index $W(G)$ of a graph $G$ is defined as the sum of distances over all pairs of vertices in $G$. It has been noted that, for many families of trees and graphs, the graphs that achieve the largest number of subtrees are exactly those that attain the smallest Wiener index, and vice versa. Consequently, it is often said that the subtree number and the Wiener index have a ”negative” correlation. In this paper, we show that, except for extremal graphs, this ”negative” correlation does not generally hold. In particular, for every $n \ge 14$, we construct a pair of unicyclic graphs $G$ and $H$, each having n vertices and identical degree sequences, such that $W(G) < W(H)$ and $N(G) < N(H)$. Furthermore, our construction shows that both differences, $N(H) − N(G)$ and $W(H) -W(G)$, grow unbounded as $n$ increases.

• Jezik: Angleški jezik
• Ključne besede: subtree number, Wiener index
• 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
• Datum objave: 01.01.2026
• Leto izida: 2026
• Št. strani: Str. 972-974
• Številčenje: Vol. 96, iss. 3
• PID: 20.500.12556/RUL-182186
• UDK: 519.17
• ISSN pri članku: 3009-4399
• DOI: 10.46793/match.96-3.25225
• COBISS.SI-ID: 276693507
• Datum objave v RUL: 29.04.2026

Gradivo je del revije

• Naslov: Match
• Skrajšan naslov: Match
• Založnik: Faculty of Science, University of Kragujevac
• ISSN: 3009-4399
• COBISS.SI-ID: 186294787

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.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: teorija grafov, drevesa, Wienerjev indeks