Spanning cubic graph designs

被引：3

作者：

Adams, Peter ^{[1
]}

Ardal, Hayri ^{[2
]}

Manuch, Jan ^{[3
]}

Hoa, Vu Dinh ^{[5
]}

Rosenfeld, Moshe ^{[4
]}

Stacho, Ladislav ^{[2
]}

机构：

[1] Univ Queensland, Dept Math, Brisbane, Qld 4072, Australia

[2] Simon Fraser Univ, Dept Math, Burnaby, BC V5A 1S6, Canada

[3] Simon Fraser Univ, Sch Comp Sci, Burnaby, BC V5A 1S6, Canada

[4] Univ Washington, Inst Technol, Tacoma, WA USA

[5] Hanoi Univ Educ, Dept Informat Technol, Hanoi, Vietnam

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 18期

基金：

澳大利亚研究理事会; 加拿大自然科学与工程研究理事会;

关键词：

Graph decomposition; Block designs; Cubic graph; Complete graph; OBERWOLFACH PROBLEM; FACTORIZATIONS; PROOF;

D O I：

10.1016/j.disc.2008.07.031

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Graph designs are natural extensions of BIBDs (balanced incomplete block designs). In this paper we explore spanning cubic graph designs and develop tools for constructing some of them. We show that K-16 can be decomposed into each of the 4060 connected cubic graphs of order 16, and into precisely 144 of the 147 disconnected cubic graphs of order 16. We also identify some infinite families of cubic graphs of order 6n + 4 that decompose K6n+4, (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：5781 / 5788

页数：8

共 24 条

[1] Cube factorizations of complete graphs
Adams, P
Bryant, D
Maenhaut, B
[J]. JOURNAL OF COMBINATORIAL DESIGNS, 2004, 12 (05) : 381 - 388
[2] ADAMS P, SPANNING CUBIC GRAPH
[3] Adams P., 1997, C NUMER, V127, P23
[4] On the Oberwolfach problem with two similar length cycles
Bryant, DE
[J]. GRAPHS AND COMBINATORICS, 2001, 17 (02) : 199 - 206
[5] Hamiltonian decompositions of prisms over cubic graphs
Cada, R
Kaiser, T
Rosenfeld, M
Ryjácek, Z
[J]. DISCRETE MATHEMATICS, 2004, 286 (1-2) : 45 - 56
[6] Graph decomposition is NP-complete: A complete proof of Holyer's conjecture
Dor, D
Tarsi, M
[J]. SIAM JOURNAL ON COMPUTING, 1997, 26 (04) : 1166 - 1187
[7] Gvozdjak P., 2004, THESIS S FRASER U
[8] On resolvable designs (Reprinted from Discrete Mathematics, vol 3, pg 343-357, 1972)
Hanani, H
Ray-Chaudhuri, DK
Wilson, RM
[J]. DISCRETE MATHEMATICS, 2006, 306 (10-11) : 876 - 885
[9] A QUICK PROOF THAT K10 NOT-EQUAL P+P+P
HANSON, D
[J]. DISCRETE MATHEMATICS, 1992, 101 (1-3) : 107 - 108
[10] Hell P., 1972, Discrete Math., V2, P229

← 1 2 3 →