3-star factors in random d-regular graphs

被引：5

作者：

Assiyatun, Hilda ^{[1
]}

Wormald, Nicholas

机构：

[1] Inst Teknol Bandung, Dept Math, Bandung 40132, Indonesia

[2] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

[3] Univ Melbourne, Dept Math & Stat, Parkville, Vic 3052, Australia

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2006年 / 27卷 / 08期

关键词：

D O I：

10.1016/j.ejc.2006.05.003

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (c) 2006 Elsevier Ltd. All rights reserved.

引用

页码：1249 / 1262

页数：14

共 17 条

[1]

[Anonymous], RANDOM GRAPHS

[2]

ASSIYATUN H, 2002, THESIS U MELBOURNE

[3] ASYMPTOTIC NUMBER OF LABELED GRAPHS WITH GIVEN DEGREE SEQUENCES [J].

BENDER, EA ;

CANFIELD, ER .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1978, 24 (03) :296-307

[4]

Bollobas B, 1985, RANDOM GRAPHS

[5] Generating and counting Hamilton cycles in random regular graphs [J].

Frieze, A ;

Jerrum, M ;

Molloy, M ;

Robinson, R ;

Wormald, N .

JOURNAL OF ALGORITHMS, 1996, 21 (01) :176-198

[6]

Garmo H, 1999, RANDOM STRUCT ALGOR, V15, P43, DOI 10.1002/(SICI)1098-2418(199908)15:1<43::AID-RSA3>3.3.CO

[7]

2-J

[8]

GARMO H, 1998, THESIS UPPSALA U SWE

[9]

Janson S., 1995, Combinatorics, Probability and Computing, V4, P369

[10]

Molloy MSO, 1997, RANDOM STRUCT ALGOR, V10, P305, DOI 10.1002/(SICI)1098-2418(199705)10:3<305::AID-RSA1>3.0.CO

← 1 2 →