Publication Date:
2013-12-27
Description:
A set of k spanning trees rooted at the same vertex r in a graph G is called independent [and the trees are called independent spanning trees (ISTs)] if, for any vertex x != r , the k paths from x to r , one path in each tree, are internally disjoint. The design of ISTs on graphs has applications to fault-tolerant broadcasting and secure message distribution in networks. It was conjectured that, for any k -connected graph, there exist k ISTs rooted at any vertex of the graph. The conjecture has been proved true for k -connected graphs with k ≤ 4, and remains open otherwise. In this paper, we deal with the problem of constructing ISTs on the Cartesian product of a sequence of hybrid graphs, including cycles and complete graphs. Consequently, this result generalizes a number of previous works. Moreover, the construction is shown to be optimal in the sense that the heights of ISTs are minimized.
Print ISSN:
0010-4620
Electronic ISSN:
1460-2067
Topics:
Computer Science
Permalink
