- View PDF version of TR-2001-12 (189405 bytes)
- View PostScript version of TR-2001-12
- Save PostScript version of TR-2001-12
- Save gzipped PostScript version of TR-2001-12 (78648 bytes)

- Enumeration of Matchings in the Incidence Graphs of Complete and Complete Bipartite Graphs, September 10, 2001 Nicholas Pippenger, 23 pages
Enumeration of Matchings in the Incidence Graphs of Complete and Complete Bipartite Graphs Nicholas Pippenger If G = (V, E) is a graph, the incidence graph I(G) is the graph with vertices the union of V and E and an edge joining v in V and e in E when and only when v is incident with e in G. For G equal to K_n (the complete graph on n vertices) or K_{n,n} (the complete bipartite graph on n + n vertices), we enumerate the matchings (sets of edges, no two having a vertex in common) in I(G), both exactly (in terms of generating functions) and asymptotically. We also enumerate the equivalence classes of matchings (where two matchings are considered equivalent if there is an automorphism of G that induces an automorphism of I(G) that takes one to the other).

If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.