\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<v, u,v \in V(G)}{d(u,v)}.
$$

Define
$$W(u,v) = \{x \in V(G)| d(u,x) < d(v,x)\}.$$
Let $w(u,v)$ denote the number of vertices that are closer to $u$ than to $v$,
i.e. $w(u,v) := |W(u,v)|$.
Hence, $w(v,u)$ is the number of vertices
that are closer to $v$ than to $u$: $w(v,u) := |W(v,u)|$.

\begin{Proposition}
For any connected graph $G$ and any pair of distinct vertices $u$ and $v$ the sets
$W(u,v)$ and $W(v,u)$ are non-empty and disjoint.
\end{Proposition}

We may define : $O(u,v) := V(G) - W(u,v) - W(v,u)$. Clearly, $O(u,v) = O(v,u)$ and
the sets $O(u,v), W(u,v), W(v,u)$ form the so-called {\em fundamental partition}
of the vertex set $V(G)$. Note that sometimes these three sets are denoted by
$_uW_v, W_{uv}, W_{vu}$, respectively; see, for instance \cite{ImrKla}.

Let $T$ be a tree. Let $e = u \sim v$ be any of its edges joining adjacent
vertices $u$ and $v$. The Wiener index $W(T)$ of $T$ can be computed as

$$W(T) = \sum_{u \sim v \in E(G)}w(u,v) w(v,u)$$

based on the following theorem (that was known already to Wiener \cite{Wiener}).

\begin{Theorem}
\label{thm:folklore}
For any tree $T$
$$W(T) = \sum_{u \sim v \in E(G)}w(u,v) w(v,u) = \sum_{u < v, u,v \in V(T)}{d(u,v)}$$
\end{Theorem}

For instance, this theorem was the basis for efficient computation of the Wiener
index for trees \cite{wienerG2}. Wiener never applied his index to connected
graphs that are not trees. So one can extend his definition to graphs arbitrarily,
the only restriction is that it should behave as the Wiener index on trees.

The invariant:

$$Sz(G) = \sum_{u \sim v \in E(G)}{w(u,v) w(v,u)}$$

is called the {\em Szeged index} of a graph \cite{Gutman}. In \cite{Randic} M.
Randi\'{c} proposed a modification of the Szeged index and called the resulting
index the {\em revised Wiener index}. However, we feel the newly described index
arises from the Szeged index and therefore should be called {\em the revised
Szeged index} $Sz^*(G)$. Let $o(u,v) = o(v,u)$ denote the number of vertices of the
same distance from $u$ and from $v$:

$$o(u,v) = |\{x \in V(G)| d(u,x) = d(v,x)\}| = |O(u,v)|$$

The revised Szeged index is defined as follows:

$$Sz^*(G) = \sum_{u \sim v \in E(G)}{(w(u,v)+ (1/2)o(u,v)) (w(v,u)+ (1/2)o(u,v))}$$

In this note we study relationships among the Wiener index, the Szeged index and
the revised Szeged index. Independent proofs of some of the results that were
obtained by Dobrynin and Gutman \cite{DobryninGutman} are presented.

\section{Edge Contributions}

If we compare the three indices: $W(G), Sz(G)$ and $Sz^*(G)$ we see that the
Szeged and the revised Szeged index can be naturally described as a sum over the
corresponding {\em edge contributions}. For an edge $e = u \sim v$ define:
$$s(e) = w(u,v) w(v,u)$$ and
$$s^*(e) = (w(u,v)+ (1/2)o(u,v)) (w(v,u)+ (1/2)o(u,v))$$

Then
$$Sz(G) = \sum_{e \in E(G)}{s(e)}$$
and
$$Sz^*(G) = \sum_{e \in E(G)}{s^*(e)}$$

\noindent
In what follows here we try to mimic the edge-contribution for the
Wiener index. Let $a$ and $b$ be two vertices of graph $G$ and let $p(a,b)$ denote
the number of shortest paths in $G$ between $a$ and $b$ and let $k(a,b,e)$ be the
number of shortest paths between $a$ and $b$ passing through the edge $e$. Define
the {\em edge contribution} $w(e)$ as

$$w(e) := \sum_{a<b, a,b \in V(G)} k(a,b,e)/p(a,b)$$

\begin{Lemma}
$$d(a,b)= \sum_{e \in E(G)} k(a,b,e)/p(a,b)
$$
\end{Lemma}

\begin{Theorem}
$$\sum_{e \in E(G)}w(e) = W(G)
$$
\end{Theorem}

\noindent
\Proof
\begin{eqnarray}
\sum_{e \in E(G)}w(e) &=& \sum_{e \in E(G)} \sum_{a<b, a,b \in V(G)} k(a,b,e)/p(a,b) = \nonumber \\
                      &=&\sum_{a<b, a,b \in V(G)} \sum_{e \in E(G)} k(a,b,e)/p(a,b) =
                          \sum_{a<b, a,b \in V(G)} d(a,b) = \nonumber \\
                      &=& W(G) \nonumber
\end{eqnarray}
\qed

\section{Results}

\noindent
Let us present the results from \cite{PisanskiRandic}.

\begin{Theorem}
For a connected graph $G$ we have $$Sz(G) \leq Sz^*(G)
$$
The equality holds if and only if $G$ is bipartite.
\end{Theorem}

\noindent
The proof obviously follows from the fact the $s(e) \leq s^*(e)$ for each edge $e$.

\begin{Theorem}
\label{thm:equality} For a tree $T$ the three indices are the same:
$$W(T) = Sz(T) = Sz^*(T)
$$
\end{Theorem}

\noindent
For general graphs the difference between the revised Szeged index and
the original Szeged index may be quite large. Take for instance the complete graph
$K_n$. The revised Szeged index is in this case equal to $Sz^*(K_n) = n^3(n-1)/8$
while $W(G) = Sz(G) = n(n-1)/2$. The quotient between the revised Szeged index and
the original index is hence $n^2$.

This example shows that the leftmost equality may hold even for graphs that are
not trees. However, it would be interesting to investigate the graphs, for which
$W(G) = Sz^*(G)$. This equality clearly holds for trees. It would be interesting
to know if such an equality may hold for any other graphs.

In a similar way one can compute the Szeged and the revised Szeged index for a
cycle graph $C_n$: $Sz(C_n) = n (\lfloor (n/2) \rfloor)^2$ and $Sz^*(C_n) =
n^3/4$. The Wiener index for cycles is $W(C_n) = n^3/8$ for even $n$ and $W(C_n) =
(n^2-1)n/8$  for odd values of $n$; see \cite{Zerovnik}.

In \cite{GraovacPisanski} the authors have used symmetry of graphs in order to
simplify the calculation of the Wiener index of a graph. In \cite{Zerovnik}, the
process has been repeated for the Szeged index, see also \cite{PisanskiRandic} for
corrections of some errors.

Now we explore the relationship between $w(e)$ and $s(e)$.

\begin{Lemma}
For every connected graph $G$ and for every edge $e = u \sim v$ it follows that
$$w(e) \leq s(e).$$
The equality holds if and only if $e$ is the only edge between $W(u,v)$ and
$W(v,u)$ and each vertex  $w \in O(u,v)$ adjacent to some vertex from $W(u,v) \cup
W(v,u)$ determines a triangle $K_3$ on $\{u,v,w\}$.
\end{Lemma}
\noindent
\Proof
$$w(e) := \sum_{a \in V(G), b \in V(G)} k(a,b,e)/p(a,b)$$
$$ \leq \sum_{a \in W(u,v), b \in W(v,u)} k(a,b,e)/p(a,b) \leq \sum_{a \in W(u,v), b
\in W(v,u)} 1  = w(u,v) w(v,u) = s(e)$$ The tricky part is to determine when
$$w(e) = s(e).$$ The leftmost inequality becomes equality if and only if the
existence of a shortest path between $a$ and $b$ passing through $e$ implies that
all shortest paths from $a$ to $b$ pass through $e$. The second inequality turning
into equality implies that for each vertex $a$ from $W(u,v)$ and for each vertex
$b$ from $W(v,u)$ at least one shortest path between them passes through $e$. This
implies that $e$ is the only edge joining $W(u,v)$ with $W(v,u)$. If $O(u,v)$ is
non-empty, it must have a vertex $w$ that is connected both to $W(u,v)$ and
$W(v,u)$ and forms an odd cycle including the edge $e$. Let $u' \in W(u,v)$ be
adjacent to $w$ and let $v' \in W(v,u)$ be adjacent to $w$. The distance between
$u'$ and $v'$ is 2 and the shortest path does not involve $e$. This means the
equality cannot hold if $O(u,v)$ is nonempty. \qed
\medskip

\noindent
Using the above Lemma one can prove the following inequality that was
proven already in \cite{KRG}, see also \cite{DobryninGutman}.

\begin{Theorem}
For any connected graph $G$ we have
$$W(G) \leq Sz(G)$$
The equality holds for graphs with the following property. $G$ is obtained from
complete graphs by vertex identifications. Two maximal complete graphs have at
most one vertex in common. Each cycle lies in a complete graph.
\end{Theorem}

\begin{Corollary}
For any connected graph $G$ we have
$$W(G) = Sz^*(G)$$
if and only if $G$ is a tree.
\end{Corollary}

\section{Arboreality of a graph}
In \cite{PisanskiRandic} the quotient $ \beta(G) = Sz(G)/Sz^*(G)$ is considered as
a measure of bipartivity of a graph. Since $0 \leq Sz(G)/Sz^*(G) \leq 1$ and
$Sz(G)/Sz^*(G) = 1$ only for bipartite graphs, it measures how close to a bipartite
graph a given graph is. The question can be asked what is the minimum value of $\beta(G)$ for
some classes of graphs.

There are two quotients that we may consider in a similar way:
$$\alpha(G) = W(G)/Sz(G)$$
and
$$\tau(G) = W(G)/Sz^*(G)$$
While $\alpha(G)$ measures how far from a tree composed of complete graphs is $G$,
$\tau(G)$ measures the departure of $G$ from a tree. Let us call it {\em
arboreality} of $G$. We may say that low $\alpha(G)$ means that $G$ is hollow,
while large values mean it is dense. Obviously, $\alpha(G)  \beta(G) = \tau(G)$
for any graph $G$.

The following tables lists some values of these parameters for certain graphs.
First we look at the complete graphs $K_n$.

\medskip

\noindent
\begin{tabular}{||l|l|l|l|l|l|l||}
\hline
$G$ & $W(G)$ & $Sz(G)$ & $Sz^*(G)$ & $\alpha(G)$ & $\beta(G)$ & $\tau(G)$ \\
\hline
$K_n$ &$n(n-1)/2$&$n(n-1)/2$&$n^3(n-1)/8$& 1 &$8/n^2$ & $8/n^2$ \\
$K_2$ &  1   &  1   &  1         &  1   &  1            &  1  \\
$K_3$ &  3   &  3   &  6.75      &  1   &  0.444444     &  0.444444    \\
$K_4$ &  6   &  6   &  24        &  1   &  0.25         &  0.25    \\
$K_5$ &  10  &  10  &  62.5      &  1   &  0.16         &  0.16    \\
$K_6$ &  15  &  15  &  135       &  1   &  0.111111     &  0.111111    \\
$K_7$ &  21  &  21  &  257.25    &  1   &  0.0816327    &  0.0816327   \\
$K_8$ &  28  &  28  &  448       &  1   &  0.0625       &  0.0625  \\
$K_{9}$ & 36 &  36  &  729       &  1   &  0.0493827    &  0.0493827   \\
\hline
\end{tabular}

\medskip

\noindent
Next we consider complete bipartite graphs $K_{n,n}$

\medskip

\noindent
\begin{tabular}{||l|l|l|l|l|l|l||}
\hline
$G$ & $W(G)$ & $Sz(G)$ & $Sz^*(G)$ & $\alpha(G)$ & $\beta(G)$ & $\tau(G)$ \\
\hline
%$K_{n,n,\dots,n}$ &$nr(nr + n - 2)/2 $&$r(r-1)n^4/2$&$r^3(r-1)n^4/8$&&&\\
$K_{n,n}$ &$n(3n - 2) $ & $n^4$ & $n^4$&$(3n - 2)/n^3$ &1 &$(3n - 2)/n^3$ \\
$K_{1,1}$ &  1   &  1   &  1   &  1.   &  1.   &  1.  \\
$K_{2,2}$ &  8   &  16  &  16  &  0.5  &  1.   &  0.5 \\
$K_{3,3}$ &  21  &  81  &  81  &  0.259259     &  1.   &  0.259259    \\
$K_{4,4}$ &  40  &  256     &  256     &  0.15625  &  1.   &  0.15625 \\
$K_{5,5}$ &  65  &  625     &  625     &  0.104    &  1.   &  0.104   \\
$K_{6,6}$ &  96  &  1296    &  1296    &  0.0740741    &  1.   &  0.0740741   \\
$K_{7,7}$ &  133     &  2401    &  2401    &  0.0553936    &  1.   &  0.0553936   \\
$K_{8,8}$ &  176     &  4096    &  4096    &  0.0429688    &  1.   &  0.0429688   \\
$K_{9,9}$ &  225     &  6561    &  6561    &  0.0342936    &  1.   &  0.0342936   \\
$K_{10,10}$ &  280     &  10000   &  10000   &  0.028    &  1.   &  0.028   \\
\hline
\end{tabular}

\medskip

\noindent
In the next table are the hypercube graphs.

\medskip

\noindent
\begin{tabular}{||l|l|l|l|l|l|l||}
\hline
$G$ & $W(G)$ & $Sz(G)$ & $Sz^*(G)$ & $\alpha(G)$ & $\beta(G)$ & $\tau(G)$ \\
\hline
$Q_n$ & & & & & & \\
$Q_1$ &  1.   &  1.   &  1.   &  1.   &  1.   &  1.  \\
$Q_2$ &  8.   &  16.  &  16.  &  0.5  &  1.   &  0.5 \\
$Q_3$ &  48.  &  192.     &  192.     &  0.25     &  1.   &  0.25    \\
$Q_4$ &  256.     &  2048.    &  2048.    &  0.125    &  1.   &  0.125   \\
$Q_5$ &  1280.    &  20480.   &  20480.   &  0.0625   &  1.   &  0.0625  \\
$Q_6$ &  6144.    &  196608.  &  196608.  &  0.03125  &  1.   &  0.03125 \\
\hline
\end{tabular}

\medskip

\noindent
In the next table with paths, only 1's appear in the columns
$\alpha(G)$, $\beta(G)$, and $\tau(G)$ because all paths are trees.

\medskip

\noindent
\begin{tabular}{||l|l|l|l|l|l|l||}
\hline
$G$ & $W(G)$ & $Sz(G)$ & $Sz^*(G)$ & $\alpha(G)$ & $\beta(G)$ & $\tau(G)$ \\
\hline
$P_n$ & & & & & & \\
$P_2$ &  1.   &  1.   &  1.   &  1.   &  1.   &  1.  \\
$P_3$ &  4.   &  4.   &  4.   &  1.   &  1.   &  1.  \\
$P_4$ &  10.  &  10.  &  10.  &  1.   &  1.   &  1.  \\
$P_5$ &  20.  &  20.  &  20.  &  1.   &  1.   &  1.  \\
$P_6$ &  35.  &  35.  &  35.  &  1.   &  1.   &  1.  \\
$P_7$ &  56.  &  56.  &  56.  &  1.   &  1.   &  1.  \\
$P_8$ &  84.  &  84.  &  84.  &  1.   &  1.   &  1.  \\
$P_9$ &  120.     &  120.     &  120.     &  1.   &  1.   &  1.  \\
$P_10$ &  165.     &  165.     &  165.     &  1.   &  1.   &  1.  \\
\hline
\end{tabular}

\medskip

\noindent
Cycles:

\medskip

\noindent
\begin{tabular}{||l|l|l|l|l|l|l||}
\hline
$G$ & $W(G)$ & $Sz(G)$ & $Sz^*(G)$ & $\alpha(G)$ & $\beta(G)$ & $\tau(G)$ \\
\hline
$C_n$ & & & & & & \\
$C_3$ &  3.   &  3.   &  6.75     &  1.   &  0.444444     &  0.444444    \\
$C_4$ &  8.   &  16.  &  16.  &  0.5  &  1.   &  0.5 \\
$C_5$ &  15.  &  20.  &  31.25    &  0.75     &  0.64     &  0.48    \\
$C_6$ &  27.  &  54.  &  54.  &  0.5  &  1.   &  0.5 \\
$C_7$ &  42.  &  63.  &  85.75    &  0.666667     &  0.734694     &  0.489796    \\
$C_8$ &  64.  &  128.     &  128.     &  0.5  &  1.   &  0.5 \\
$C_9$ &  90.  &  144.     &  182.25   &  0.625    &  0.790123     &  0.493827    \\
$C_{10}$ &  125.     &  250.     &  250.     &  0.5  &  1.   &  0.5 \\
$C_{11}$ &  165.     &  275.     &  332.75   &  0.6  &  0.826446     &  0.495868    \\
$C_{12}$ &  216.     &  432.     &  432.     &  0.5  &  1.   &  0.5 \\
$C_{13}$ &  273.     &  468.     &  549.25   &  0.583333     &  0.852071     &  0.497041    \\
$C_{14}$ &  343.     &  686.     &  686.     &  0.5  &  1.   &  0.5 \\
$C_{15}$ &  420.     &  735.     &  843.75   &  0.571429     &  0.871111     &  0.497778    \\
\hline
\end{tabular}

\medskip

\noindent
Some generalized Petersen graphs.

\medskip

\noindent
\begin{tabular}{||l|l|l|l|l|l|l||}
\hline
graph & $W(G)$ & $Sz(G)$ & $Sz^*(G)$ & $\alpha(G)$ & $\beta(G)$ & $\tau(G)$ \\
\hline
$P(3,1)$  &  21.  &  51.  &  81.  &  0.411765     &  0.62963  &  0.259259    \\
$P(4,1)$&  48.  &  192.     &  192.     &  0.25     &  1.   &  0.25    \\
$P(5,1)$ &  85.  &  285.     &  375.     &  0.298246     &  0.76     &  0.226667    \\
$P(5,2)$ &  75.  &  135.     &  375.     &  0.555556     &  0.36     &  0.2 \\
$P(6,1)$ &  144.     &  648.     &  648.     &  0.222222     &  1.   &  0.222222    \\
$P(6,2)$ &  135.     &  354.     &  634.5    &  0.381356     &  0.55792  &  0.212766    \\
$P(7,1)$ &  217.     &  847.     &  1029.    &  0.256198     &  0.823129     &  0.210884    \\
$P(7,2)$ &  189.     &  602.     &  1029.    &  0.313953     &  0.585034     &  0.183673    \\
$P(8,1)$ &  320.     &  1536.    &  1536.    &  0.208333     &  1.   &  0.208333    \\
$P(8,2)$ &  280.     &  856.     &  1528.    &  0.327103     &  0.560209     &  0.183246    \\
$P(8,3)$ &  272.     &  1536.    &  1536.    &  0.177083     &  1.   &  0.177083    \\
\hline
\end{tabular}


\medskip

\noindent
The following comparison of the three indices is taken from Pisanski and
Randi\' c \cite{PisanskiRandic}.

\medskip

%\begin{figure}[hhht]
%\centering
%\begin{small}

\noindent
\begin{tabular}{|c|c|c|c|}
\hline
    & Wiener index & Szeged Index & Revised Szeged index\\
    \hline
    source & \cite{Wiener} & \cite{Gutman} & \cite{Randic} \\
   \hline
    notation & $W(G)$ & $Sz(G)$ & $Sz^*(G)$ \\
 \hline
    $G = P_n$ &$(n^3-n)/6$&$(n^3-n)/6$&$(n^3-n)/6$\\
    \hline
    $G = C_n$, $n$ even &$n^3/8$&$n^3/4$&$n^3/4$\\
    \hline
    $G = C_n$, $n$ odd &$(n^3-n)/8$&$n(n-1)^2/4$&$n^3/4$\\
    \hline
    $G = K_n$ &$n(n-1)/2$&$n(n-1)/2$&$n^3(n-1)/8$\\
   \hline
    $G = H \square K$ &$W(K)|V(H)|^2 +  $&$W(K)|V(H)|^3 +  $&$W(K)|V(H)|^3 +  $\\
                      &$ + W(H)|V(K)|^2$ &$ + W(H)|V(K)|^3$ &$ + W(H)|V(K)|^3$\\
    \hline
    $G^k$ &$kW(G)|V(G)|^{2(k-1)} $&$kSz(G)|V(G)|^{3(k-1)} $&$kSz^*(G)|V(G)|^{3(k-1)} $\\
    \hline
    $G = Q_n$ &$n2^{2(n-1)}$&$n2^{3(n-1)} $&$n2^{3(n-1)}$\\
    \hline
    $G = K_{n,n,\dots,n}$ &$nr(nr + n - 2)/2 $&$r(r-1)n^4/2$&$r^3(r-1)n^4/8$\\
   \hline
    $G$ bipartite &$$&$Sz(G)$&$Sz(G)$\\
    \hline
    $T$ tree &$W(T)$&$W(T)$&$W(T)$\\
    \hline
  \end{tabular}
%\end{small}
%\centering \caption{Comparison of the three indices. Taken from Pisanski and Randi\' c} \label{comparison}
%\end{figure}
\medskip

\section{Conclusion}

There is a natural difference between the Wiener index and the other indices
described above. For the Wiener index one may usually compute the contribution of
each vertex and then sum the contributions. In the Szeged index one may compute an
edge contribution and then sum the obtained edge contributions. The same is true
for the revised Szeged index. However, this distinction is not absolute. The
latter approach may be used for the Wiener index as shown in
\cite{PisanskiZerovnik} however, the computations are more involved. We hope we
can use this approach to study more closely the relationship between the indices
$W(G), Sz(G)$ and $Sz^*(G)$.

In \cite{CK} the authors have computed the Wiener index and the Szeged index for
benzenoid graphs in linear time.
It is clear that their methods give also the
revised Szeged index since all benzenoids are bipartite.
It is well-known that on trees, the Wiener index
can be computed in linear time \cite{wienerG2}, and, consequently, the Szeged indices on trees
can be computed in linear time.
In general, the Wiener and Szeged indices can be computed in time $O(mn)$
\cite{janezCCA}. The revised Szeged index can be computed within the same time complexity by a
straightforward method using the distance matrix.
The question is whether the computation of the revised Szeged index
can  be done faster  for  some  classes of graphs.


%In the paper some basic properties and computations of the revised Szeged index
%are presented. We also corrected some errors from \cite{Zerovnik}.

\section{Acknowledgements} The authors would like to thank Sandi Klav\v{z}ar and
Milan Randi\'{c} for careful reading of the manuscript and many useful
suggestions. The authors acknowledge partial funding of this research via ARSS of
Slovenia, grants: L2-7230,P1-0294,L2-7207 and the PASCAL network of excellence in
the 6th framework.


\begin{thebibliography}{99}


\bibitem{corona} J.~Brunvoll,  B.~N.~Cyvin, S.~J.~Cyvin,  Enumeration and
Classification of Coronoid Hydrocarbons, \emph{J.\ Chem.\ Inf.\ Comput.\ Sci.}
(1987) \textbf{27}, 14--21.

\bibitem{CK}
V.~Chepoi, S.~Klav\v{z}ar, The Wiener index and the Szeged index of benzenoid
systems in linear time, {\em J. Chem. Inf. Comput. Sci.} {\bf 37} (1997) 752--755.


\bibitem{DobryninGutman} A.~A.~Dobrynin and I.~Gutman, Solving a problem connected
with distances in graphs, \emph{Graph Theory Notes New York} \textbf{XXVIII (5)}
(1994) 21--23.

\bibitem{Dobrynin} A.~A.~Dobrynin, Graphs Having the Maximal Value of the Szeged
Index,  \emph{Croatica Chemica Acta} \textbf{70} (1997) 819--825.

\bibitem{outerplanar} H.~J.~Fleischner, D.~P.~Geller, F.~Harary,
Outerplanar graphs and weak duals, \emph{J.\ Indian Math.\ Soc.\ (N.S.)}
\textbf{38} (1974), 215--219.

\bibitem{GraovacPisanski} A.~Graovac, T.~Pisanski, On the Wiener index of a graph,
{\em J. Math. Chem.} {\bf 8} (1991),
53--62.

\bibitem{GT}
J.~L.~Gross, T.~W.~Tucker,
{\em Topological Graph Theory,} Wiley Intersicence, 1987.


\bibitem{theory} J.~J.~Gross, J.~Yellen (Editors) \emph{Handbook of graph theory,}
Boca Raton [etc.], CRC Press,
2004.

\bibitem{Gutman} I.~Gutman, A formula for the Wiener number of trees and its extension to graphs
containing cycles, \emph{Graph Theory Notes},  1994, 27, 9.

\bibitem{wienerC2} I.~Gutman and S.~Klav\v{z}ar, A method for calculating Wiener numbers of
benzenoid hydrocarbons, \emph{Acta Chim.\ Hung.} \textbf{133} (1996) 389--399.

\bibitem{ImrKla}
W.~Imrich, S.~Klav\v{z}ar, {\em Product graphs,} Wiley-Interscience, New York,
2000.

\bibitem{KRG} S.~Klav\v{z}ar, A.~Rajapakse, I.~Gutman, The Szeged and the Wiener
index of graphs, {\em Appl. Math. Lett.} {\bf 9} (1996) 45--49.


\bibitem{luksic} P.~Luk\v{s}i\v{c}, T.~Pisanski, Distance-residual graphs,
\emph{arXiv:math/0609810}, 2006.

\bibitem{wienerG2} B.~Mohar and T.~Pisanski, How to compute the Wiener index of a graph,
\emph{J.\ Math.\ Chem.} \textbf{2} (1988) 267--277.

\bibitem{vega}
T.~Pisanski \& coworkers, \textsc{Vega}, a programming tool for manipulating
discrete mathematical structures, see \verb+http://vega.ijp.si+.

\bibitem{PisanskiRandic} T.~Pisanski and M.~Randi\'{c}, Use of the Szeged index and the revised Szeged index for measuring network bipartivity,
\emph{Discrete Appl. Math.}, to appear.

\bibitem{pis} T.~Pisanski, T.~W.~Tucker,
Growth in products of graphs. \emph{Australas.\ J.\ Combin.} \textbf{26} (2002),
155--169.

\bibitem{PisanskiZerovnik} T.~Pisanski and J.~\v{Z}erovnik, Weights on edges of chemical
graphs determined by paths,  \emph{J. Chem. Inf. Comput. Sci.}, {\bf 34} (1994)
395--397.

\bibitem{Randic1}  M.~Randi\'{c}, Characterization of molecular branching, \emph{J. Am. Chem. Soc.} 1975, 97, 6609.

\bibitem{Randic}
M.~Randi\'{c}, On generalization of Wiener index for cyclic structures, {\em Acta
Chimica Slovenica,} {\bf 49} (2002) 483--496.


\bibitem{randic} M.~Randi\'{c}, S.~Nikoli\'{c}, N.~Trinajsti\'{c}, Enumeration of
Kekul\'{e} Structures for Helicenic Systems, \emph{Croat.\ Chem.\ Acta.} (1988)
\textbf{61}, 821--831.


\bibitem{chemtheory} N.~Trinajsti\'{c}, \emph{Chemical graph theory,} 2nd rev.\
ed. Boca Raton [etc.], CRC Press, 1992.

\bibitem{tucker}  A.~Tucker,  \emph{Applied combinatorics,} 3rd ed.,
New York [etc.], J.~Wiley, 2001.

\bibitem{Wiener}  H.~Wiener, Correlation of heats of isomerization, and differences in
heats of vaporization
of isomers, among the paraffin hydrocarons, \emph{J. Am. Chem. Soc.} 1947, 69, 17.

\bibitem{janezCCA} J.~\v{Z}erovnik,  Computing the Szeged index, \emph{Croatica Chemica Acta}, {\bf 69} (1996) 837--843.

\bibitem{Zerovnik} J.~\v{Z}erovnik, Szeged index of symmetric graphs, \emph{J. Chem. Inf. Comput. Sci.}, {\bf
39} (1999), 77--80.

\end{thebibliography}


\end{document}