Seminar in Applied Mathematics

Michael Ferrara Class of 2000 Department of Mathematical Sciences Stevens Institute of Technology Spanning Tree Edge Densities Monday, April 24, 2000 3:15pm Pierce 116

Abstract:   In the design of reliable and invulnerable networks, it is often a goal to maximize the number of spanning trees of a graph with a given number of vertices and edges. It is logical to investigate the importance of individual edges to the number of spanning trees of a graph. Given a graph G the spanning tree edge density (hereafter density) of an edge e is the fraction of the spanning trees of G that contain e. Several bounds and conditions on the densities of the edges of a graph are given. These include a lower bound, dependent only on the edge-connectivity of the graph as well as a condition on the sum of the densities. A general formula for the density of all edges of edge-transitive graphs is presented as well. Along these lines, the reliability implications of these notions will be discussed. A brief investigation of the theory of densities applied to multigraphs will be conducted. In this vein, it will be shown that for any rational number r, between zero and one, there exists a multigraph that contains an edge of density r. Finally, some basic matrix theoretic results will be introduced as well as a short summary of open problems related to this newly developed concept.

Coffee and refreshments will be available starting at 3:00pm. For additional information contact Patrick Miller  or Yi Li.