K. R. Udaya Kumar Reddy and Ranjana S. Chakrasali, BNM Institute of Technology, India

Given a simple connected undirected graph ᠳ =䙦ᡈ,ᠱ䙧 with |ᡈ|= ᡦ and|ᠱ|= ᡥ, the Wiener index ᡉ䙦ᠳ䙧 of ᠳ is defined as half the sum of the distances of the form ᡖ䙦ᡳ,ᡴ䙧 between all pairs of vertices u, v of ᠳ. If 䙦ᠳ,ᡵ〆䙧is an edge-weighted graph, then the Wiener index ᡉ䙦ᠳ,ᡵ〆䙧of 䙦ᠳ,ᡵ〆䙧 is defined as the usual Wiener index but the distances is now computed in䙦ᠳ,ᡵ〆䙧. The paper proposes a new algorithm for computing the Wiener index of a Fibonacci weighted trees with Fibonacci branching in place of the available naive algorithm for the same. It is found that the time complexity of the algorithm is logarithmic.

Algorithms, Distance in graphs, Fibonacci weighted tree, Wiener index.