\documentclass[a4paper,12pt]{article} \usepackage{latexsym} \usepackage{amsmath,amsthm,amsfonts} \usepackage{graphicx} %zbrisi \newcommand{\B}{\mathcal{B}} \newcommand{\bC}{\mathbb{C}} \newcommand{\bN}{\mathbb{N}} \newcommand{\bR}{\mathbb{R}} \newcommand{\bZ}{\mathbb{Z}} \newcommand{\C}{\mathcal{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathcal{D}} \newcommand{\R}{\mathcal{R}} \newcommand{\N}{\mathcal{N}} \newcommand{\cB}{\mathcal{B}} \newcommand{\cI}{\mathcal{I}} %\newcommand{\cD}{\mathcal{D}} %\newcommand{\cE}{\mathcal{E}} %\newcommand{\cO}{\mathcal{O}} %\newcommand{\cP}{\mathcal{P}} \newcommand{\I}{\mathrm{I}} \newcommand{\T}{\mathrm{T}} \newcommand{\quot}{/_{\!\approx}} \newcommand{\quoti}[1]{/_{\!{\approx_{#1}}}} \newcommand{\coo}[1]{\mathbf{#1}} \newcommand{\mi}[1]{\textsl{#1}} \newcommand{\mb}[1]{\textbf{#1}} \newcommand{\Vega}{{\sc Vega}} \newcommand{\figname}[1]{#1.eps} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\girth}{girth} \DeclareMathOperator{\lcm}{lcm} % definitions, theorems, ... %\theoremstyle{definition} %\newtheorem{defn}{Definition} %\newtheorem{example}{Example}[section] %\newtheorem{conjecture}{Conjecture}[section] %\newtheorem{question}{Question}[section] \theoremstyle{plain} %\newtheorem{thm}{Theorem}[section] \newtheorem{Theorem}{Theorem} \newtheorem{Corollary}[Theorem]{Corollary} \newtheorem{Proposition}[Theorem]{Proposition} \newtheorem{Observation}[Theorem]{Observation} \newtheorem{Question}{Question} \newtheorem{Problem}{Problem} \newtheorem{Lemma}[Theorem]{Lemma} \theoremstyle{remark} \newtheorem*{rem}{Remark} \newtheorem*{Remark}{Remark} \newenvironment{Proof}{{\bf Proof} \ }{\hfill $\Box$} \begin{document} \title{Edge-contributions of some topological indices \\and arboreality of molecular graphs} \author{ Toma\v{z} Pisanski,\thanks{\texttt{Tomaz.Pisanski@fmf.uni-lj.si}, IMFM, University of Ljubljana and University of Primorska}\\ and\\ Janez \v{Z}erovnik\thanks{\texttt{Janez.Zerovnik@imfm.uni-lj.si}, IMFM} } \date{ } \maketitle \begin{abstract} Some graph invariants can be computed by summing certain values, called {\em edge-contributions} over all edges of graphs. In this note we use edge-contributions to study relationships among three graph invariants, also known as topological indices in mathematical chemistry: Wiener index, Szeged index and recently introduced revised Szeged index. We also use the quotient between the Wiener index and the revised Szeged index to study arboreality (tree-likeness) of graphs. \end{abstract} \section{Introduction and Motivation} In mathematical chemistry some graph invariants are being studied intensively since they correlate well, when applied to molecular graphs, with certain properties of the corresponding molecules. In this note we explore three such invariants, all based on the Wiener index \cite{Wiener}, that was initially defined for trees and admits several non-equivalent generalizations to general graphs. Traditionally, the Wiener index for general graphs is defined as the sum of all distances in a graph. Ivan Gutman \cite{Gutman} introduced another generalization that is known under the name of {\em Szeged index}. Recently Milan Randi\'{c} modified the definition of the Szeged index. The new index was named \emph{revised Szeged index} by Pisanski and Randi\'{c} \cite{PisanskiRandic}. Let $G$ be any connected graph. Then one can define the usual distance function on its vertex set $V(G)$. Namely, $d(u,v)$ is the number of edges on any of the shortest paths joining vertex $u$ to vertex $v$. The Wiener index is defined as: $$W(G) = (1/2)\sum_{(u,v) \in V(G)\times V(G)}{d(u,v)}$$ where the sum runs over all ordered pairs of vertices. The factor $(1/2)$ is needed in order to count each pair exactly once. If we want to avoid extra work, it is more convenient to consider unordered pairs. For example, if the vertex set is linearly ordered, we can write W(G) = \sum_{u