Document Type

Article

Department

Mathematics (HMC)

Publication Date

2002

Abstract

If G = (V, E) is a graph, the incidence graphI(G) is the graph with vertices I ∪ E and an edge joining v ∈ V and e ∈ E when and only when v is incident with e in G. For G equal to Kn (the complete graph on n vertices) or Kn,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).

Rights Information

© 2002 Society for Industrial and Applied Mathematics

Download

Share

COinS