No CrossRef data available.
Article contents
Counting Matchings and Tree-Like Walks in Regular Graphs
Published online by Cambridge University Press: 10 February 2010
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
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.
Information
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2010
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
You have
Access
- 5
- Cited by