Random spanning trees on homogeneous graphs
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Spanning trees have been studied as combinatorial objects for a long time. However, they have found great use in other disciplines recently. Disjoint spanning trees are important in fault-tolerant broadcasting or load-balancing communication systems in interconnection networks. For instance, providing completely independent spanning trees (pairwise edge-disjoint and internally disjoint spanning trees) guarantees uninterrupted service. Completely independent spanning trees were introduced by T. Hasunuma and then have been studied on different classes of graphs. The problem to determine whether there exist two completely independent spanning trees in a graph G is NP-hard . In this context, one may aim to construct spanning trees that collide as little as possible. This problem has been studied by Albin, Poggi-Corradini, et al.. Here we think of spanning trees of a graph as random variables and we aim to find a probability mass function (pmf) that minimizes the expected overlap of two random spanning trees.
We study the minimum expected overlap problem for a special class of graphs. We provide a necessary and sufficient condition for a homogeneous graph to admit optimal weights. Given an unweighted graph
In addition, we show that the objective function of the minimum expected overlap problem is quasiconvex in each coordinate. Essentially, we show that there is a unique minimizer which allows us to introduce convergent algorithms to compute the optimal weights.