3-star factors in random d-regular graphs

Hilda Assiyatun, Nicholas Wormald

Research output: Contribution to journalArticleResearchpeer-review

6 Citations (Scopus)

Abstract

The small subgraph conditioning method first appeared when Robinson and the second author showed the almost sure hamiltonicity of random d-regular graphs. Since then it has been used to study the almost sure existence of, and the asymptotic distribution of, regular spanning subgraphs of various types in random d-regular graphs and hypergraphs. In this paper, we use the method to prove the almost sure existence of 3-star factors in random d-regular graphs. This is essentially the first application of the method to non-regular subgraphs in such graphs.

Original languageEnglish
Pages (from-to)1249-1262
Number of pages14
JournalEuropean Journal of Combinatorics
Volume27
Issue number8 SPEC. ISS.
DOIs
Publication statusPublished - Nov 2006
Externally publishedYes

Cite this