Skip navigation
Skip navigation

Subgraphs of Random k-Edge-Coloured k-Regular Graphs

Lieby, Paulette; McKay, Brendan; McLeod, Jeanette C.; Wanless, Ian

Description

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]

CollectionsANU Research Publications
Date published: 2009
Type: Journal article
URI: http://hdl.handle.net/1885/52619
Source: Combinatorics Probability and Computing
DOI: 10.1017/S0963548309009882

Download

File Description SizeFormat Image
01_Lieby_Subgraphs_of_Random_2009.pdf4.96 MBAdobe PDF    Request a copy
02_Lieby_Subgraphs_of_Random_2009.pdf10.71 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  23 August 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator