On the Kirchhoff and the Wiener Indices of Graphs and Block Decomposition

被引：0

作者：

Nikseresht, Ashkan ^{[1
]}

Sepasdar, Zahra ^{[1
]}

机构：

[1] Shiraz Univ, Dept Math, Shiraz, Iran

来源：

ELECTRONIC JOURNAL OF COMBINATORICS | 2014年 / 21卷 / 01期

关键词：

Kirchhoff index; Wiener index; Resistance distance; Shortest path problem; Block Decomposition; RESISTANCE DISTANCES;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页数：13