<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume9 Issue1" %>
On the Number of Bases of Bicircular Matroids
Omer Giménez, Anna de Mier, and Marc Noy
Departament de Matem¨¤tica Aplicada II. Pau Gargallo 5, Universitat Polit¨¨cnica de Catalunya 08028 Barcelona, Spain
{omer.gimenez,anna.de.mier, marc.noy}@upc.es
Annals of Combinatorics 9 (1) p.35-45 March, 2005
AMS Subject Classification: 05B35, 05A16
Let t(G) be the number of spanning trees of a connected graph G, and let b(G) be the number of bases of the bicircular matroid
B(G). In this paper we obtain bounds relating b(G) and t(G), and study in detail the case where G is a complete graph Kn or a complete bipartite graph Kn,m.
Keywords: bicircular matroid, spanning tree, asymptotic enumeration


1. P. Flajolet and R. Sedgewick, Analytic Combinatorics (book in preparation), Individual chapters are available as INRIA Research Reports 1888, 2026, 2376, 2956, 3162, 4013 and at http://algo.inria.fr/flajolet/

2. L.R. Matthews, Bicircular matroids, Quart. J. Math. Oxford Ser. 28 (2) (1977) 213--227.

3. J.W. Moon, Counting labelled trees, Canadian mathematical monographs, Canadian Mathematical Congress, Montreal, Que. 1 1970 x+113 pp.

4. N.A. Neudauer, A.M. Meyers, and B. Stevens, Enumeration of the bases of the bicircular matroid on a complete graph, Congr. Numer. 149 (2001) 109--127.

5. N.A. Neudauer and B. Stevens, Enumeration of the bases of the bicircular matroid on a complete bipartite graph, Ars Combin. 66 (2003) 165--178.

6. J.G. Oxley, On the numbers of bases and circuits in simple binary matroids, Europ. J. Combin. 4 (1983) 169--178.

7. J.G. Oxley, Matroid Theory, Oxford University Press, Oxford, 1992.

8. R.P. Stanley, Enumerative combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.