ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P3.03
https://doi.org/10.26493/1855-3974.2882.c5e
(Also available at http://amc-journal.eu)
Comparing Wiener, Szeged and revised Szeged
index on cactus graphs
Stefan Hammer *
Graz University of Technology, Rechbauerstraße 12, Graz, Austria
Received 9 May 2022, accepted 1 November 2022, published online 11 January 2023
Abstract
We show that on cactus graphs the Szeged index is bounded above by twice the Wiener
index. For the revised Szeged index the situation is reversed if the graph class is further
restricted. Namely, if all blocks of a cactus graph are cycles, then its revised Szeged index
is bounded below by twice its Wiener index. Additionally, we show that these bounds
are sharp and examine the cases of equality. Along the way, we provide a formulation of
the revised Szeged index as a sum over vertices, which proves very helpful, and may be
interesting in other contexts.
Keywords: Wiener index, (Revised) Szeged index, cactus graphs.
Math. Subj. Class. (2020): 05C09
*Stefan Hammer acknowledges the support of the Austrian Science Fund (FWF): W1230.
E-mail address: stefan.hammer@tugraz.at (Stefan Hammer)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P3.03
https://doi.org/10.26493/1855-3974.2882.c5e
(Dostopno tudi na http://amc-journal.eu)
Primerjava Wienerjevega, Szegedovega in
revidiranega Szegedovega indeksa na kaktusnih
grafih
Stefan Hammer *
Graz University of Technology, Rechbauerstraße 12, Graz, Austria
Prejeto 9. maja 2022, sprejeto 1. novembra 2022, objavljeno na spletu 11. januarja 2023
Povzetek
Pokažemo, da je na kaktusnih grafih Szegedov indeks omejen navzgor z dvakratnikom
Wienerjevega indeksa. Za revidirani Szegedov indeks je situacija obrnjena, če razred grafov
še dodatno omejimo. Velja namreč naslednje: če so vsi bloki kaktusnega grafa cikli, potem
je njegov revidirani Szegedov indeks omejen navzdol z dvakratnikom Wienerjevega in-
deksa. Dodatno pokažemo, da so te meje ostre, in raziščemo primere, v katerih dejansko
velja enakost. Spotoma podamo formulacijo revidiranega Szegedovega indeksa v smislu
vsote nad točkami, kar se izkaže za zelo koristno, in bi lahko bilo zanimivo v drugih kon-
tekstih.
Ključne besede: Wienerjev indeks, (revidirani) Szegedov indeks, kaktusni grafi.
Math. Subj. Class. (2020): 05C09
*Stefan Hammer priznava podporo s strani Austrian Science Fund (FWF): W1230.
E-poštni naslov: stefan.hammer@tugraz.at (Stefan Hammer)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/