Name
Abstract | ||
|---|---|---|
A cylinder graph is the graph Cartesian product of a path and a cycle. In this paper we investigate the length of a minimal spanning tree of a cylinder graph whose edges are assigned random lengths according to independent and uniformly distributed random variables. Our work was inspired by a formula of J. Michael Steele which shows that the expected length of a minimal spanning tree of a connected graph can be calculated through the Tutte polynomial of the graph. First, using transfer matrices, we show how to calculate the Tutte polynomials of cylinder graphs. Second, using Steele's formula, we tabulate the expected lengths of the minimal spanning trees for some cylinder graphs. Third, for a fixed cycle length, we show that the ratio of the expected length of a minimal spanning tree of a cylinder graph to the length of the cylinder graph converges to a constant; this constant is described in terms of the Perron–Frobenius eigenvalue of the accompanying transfer matrix. Finally, we show that the length of a minimal spanning tree of a cylinder graph satisfies a strong law of large numbers. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1017/S0963548306007668 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
fixed cycle length,cylinder graph,random length,tutte polynomial,cylinder graph converges,accompanying transfer matrix,graph cartesian product,minimal spanning tree,expected length,connected graph,j. michael steele | Geometric graph theory,Discrete mathematics,Combinatorics,Line graph,Tutte polynomial,Cycle basis,Cubic graph,Spanning tree,Butterfly graph,Voltage graph,Mathematics | Journal |
Volume | Issue | ISSN |
16 | 1 | 0963-5483 |
Citations | PageRank | References |
1 | 0.36 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kevin Hutson | 1 | 1 | 1.04 |
| Thomas M. Lewis | 2 | 3 | 1.70 |