Reliability Hosoya-Wiener Polynomial of DoubleWeighted Trees

摘要

Reliability Hosoya-Wiener polynomial for edge weighted graphs is defined, that can be used as a measure of reliability of a communication network. Each edge is assigned two weights, reliability and communication delay. Some basic properties are given and a recursive formula for the reliability Hosoya-Wiener polynomial of a rooted tree is proved that yields a linear time algorithm on weighted trees. On general graphs, the reliability Hosoya-Wiener polynomial can be computed in O (n(3)) time.