Subgraphs of random k-edge-coloured k-regular graphs

Paulette Lieby, Brendan D McKay, Jeanette C McLeod, Ian Murray Wanless

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)


Let G = G(n) be a randomly chosen k-edge-coloured k-regular graph with 2n vertices, where k = k(n). Such a graph can be obtained from a random set of k edge-disjoint perfect matchings of K2n. Let h = h(n) be a graph with m = m(n) edges such that m2 + mk = o(n). Using a switching argument, we find an asymptotic estimate of the expected number of subgraphs of G isomorphic to h. Isomorphisms may or may not respect the edge colouring, and other generalizations are also presented. Special attention is paid to matchings and cycles. The results in this paper are essential to a forthcoming paper of McLeod in which an asymptotic estimate for the number of k-edge-coloured k-regular graphs for k = o(n5/6) is found.
Original languageEnglish
Pages (from-to)533 - 549
Number of pages17
JournalCombinatorics, Probability and Computing
Issue number4
Publication statusPublished - 2009

Cite this