Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-29T15:15:00.005Z Has data issue: false hasContentIssue false
  • English
  • Français

Counting Matchings and Tree-Like Walks in Regular Graphs

Published online by Cambridge University Press:  10 February 2010

IAN. M. WANLESS
IAN. M. WANLESS*
Affiliation:
School of Mathematical Sciences, Monash University, Vic 3800, Australia (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

The number of closed tree-like walks in a graph is closely related to the moments of the roots of the matching polynomial for the graph. Thus, by counting these walks up to a given length it is possible to find approximations for the matching polynomial. This approach has been used in two separate problems involving asymptotic enumerations of 1-factorizations of regular graphs. Nevertheless, a systematic way to count the required walks had not previously been found.

In this paper we give an algorithm to count closed tree-like walks in a regular graph up to a given length. For small m, this provides expressions for the number of m-matchings in the graph in terms of the numbers of copies of certain small subgraphs that appear in the graph. The simplest of these expressions were already known, having been rediscovered by numerous authors using ad hoc methods. We offer the first general method for producing the expressions. We also find generating functions that isolate the contribution from the simplest kind of subgraph – namely a single cycle of arbitrary length.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 3 , May 2010 , pp. 463 - 480
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Beezer, R. A. and Farrell, E. J. (1995) The matching polynomial of a regular graph. Discrete Math. 137 7–18.CrossRefGoogle Scholar
[2]Beezer, R. A. and Farrell, E. J. (1998) Counting subgraphs of a regular graph. J. Math. Sci. (Calcutta) 9 47–55.Google Scholar
[3]Chung, F. and Yau, S.-T. (1999) Coverings, heat kernels and spanning trees. Electron. J. Combin. 6 R12.Google Scholar
[4]Diaconis, P. and Gamburd, A. (2004) Random matrices, magic squares and matching polynomials. Electron. J. Combin. 11 R2.CrossRefGoogle Scholar
[5]Farrell, E. J., Guo, J. M. and Constantine, G. M. (1991) On matching coefficients. Discrete Math. 89 203–210.CrossRefGoogle Scholar
[6]Friedland, S., Krop, E. and Markström, K. (2008) On the number of matchings in regular graphs. Electron. J. Combin. 15 R110.CrossRefGoogle Scholar
[7]Godsil, C. D. (1981) Matchings and walks in graphs. J. Graph Theory 5 285–297.CrossRefGoogle Scholar
[8]Godsil, C. D. and McKay, B. D. (1990) Asymptotic enumeration of Latin rectangles. J. Combin. Theory Ser. B 48 19–44.CrossRefGoogle Scholar
[9]Heilmann, O. J. and Lieb, E. H. (1972) Theory of monomer–dimer systems. Comm. Math. Phys. 25 190–232.Google Scholar
[10]Macdonald, I. G. (1995) Symmetric Functions and Hall Polynomials, 2nd edn, Oxford University Press.Google Scholar
[11]McKay, B. D. (1981) The expected eigenvalue distribution of a large regular graph. Linear Algebra Appl. 40 203–216.CrossRefGoogle Scholar
[12]McKay, B. D. and Wanless, I. M. (1998) Maximising the permanent of (0,1) matrices and the number of extensions of Latin rectangles. Electron. J. Combin. 5 R11.CrossRefGoogle Scholar
[13]McLeod, J. C. Asymptotic enumeration of k-edge-coloured k-regular graphs. SIAM J. Discrete Math., to appear.Google Scholar
[14]Quenell, G. (1994) Combinatorics of free product graphs. Contemp. Math., 173 257–281.CrossRefGoogle Scholar
[15]Wanless, I. M. (1999) The Holens–Djoković conjecture on permanents fails. Linear Algebra Appl. 286 273–285.CrossRefGoogle Scholar
[16]Wanless, I. M. (1999) Maximising the permanent and complementary permanent of (0,1) matrices with constant line sum. Discrete Math. 205 191–205.Google Scholar
[17]Wanless, I. M. (2003) A lower bound on the maximum permanent in Λnk. Linear Algebra Appl. 373 153–167.Google Scholar