In this article we state a relation between the Kirchhoff and Wiener indices of a simple connected graph $G$ and the Kirchhoff and Wiener indices of those subgraphs of $G$ which are induced by its blocks. Then as an application, we define a composition of a rooted tree $T$ and a graph $G$ and calculate its Kirchhoff index in terms of parameters of $T$ and $G$. Finally, we present an algorithm for computing the resistance distances and the Kirchhoff index and a similar one for computing the weighted distances and the Wiener index of a graph. These algorithms are asymptotically faster than the previously known algorithms, on graphs in which the order of the subgraphs induced by blocks is small with respect to the order of the graph.
@article{10_37236_3508,
author = {Ashkan Nikseresht and Zahra Sepasdar},
title = {On the {Kirchhoff} and the {Wiener} indices of graphs and block decomposition},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {1},
doi = {10.37236/3508},
zbl = {1300.05086},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3508/}
}
TY - JOUR
AU - Ashkan Nikseresht
AU - Zahra Sepasdar
TI - On the Kirchhoff and the Wiener indices of graphs and block decomposition
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/3508/
DO - 10.37236/3508
ID - 10_37236_3508
ER -
%0 Journal Article
%A Ashkan Nikseresht
%A Zahra Sepasdar
%T On the Kirchhoff and the Wiener indices of graphs and block decomposition
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3508/
%R 10.37236/3508
%F 10_37236_3508
Ashkan Nikseresht; Zahra Sepasdar. On the Kirchhoff and the Wiener indices of graphs and block decomposition. The electronic journal of combinatorics, Tome 21 (2014) no. 1. doi: 10.37236/3508
