Subgraphs of Random k-Edge-Coloured k-Regular Graphs
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...[Show more]
|Collections||ANU Research Publications|
|Source:||Combinatorics Probability and Computing|
|01_Lieby_Subgraphs_of_Random_2009.pdf||4.96 MB||Adobe PDF||Request a copy|
|02_Lieby_Subgraphs_of_Random_2009.pdf||10.71 kB||Adobe PDF||Request a copy|
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.