Vertex-transitive graphs that have no Hamilton decomposition

被引：4

作者：

Bryant, Darryn ^{[1
]}

Dean, Matthew ^{[1
]}

机构：

[1] Univ Queensland, Sch Math & Phys, Brisbane, Qld 4072, Australia

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2015年 / 114卷

基金：

澳大利亚研究理事会;

关键词：

Hamilton decompositions; Hamilton cycles; Vertex-transitive graphs; Cayley graphs; 6-REGULAR CAYLEY-GRAPHS; ABELIAN-GROUPS; ODD ORDER; CYCLE DECOMPOSITION; VERTICES;

D O I：

10.1016/j.jctb.2015.05.007

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It is shown that there are infinitely many connected vertex-transitive graphs that have no Hamilton decomposition, including infinitely many Cayley graphs of valency 6, and including Cayley graphs of arbitrarily large valency. (C) 2015 Elsevier Inc. All rights reserved.

引用

页码：237 / 246

页数：10

共 39 条

[1] ON HAMILTON DECOMPOSITIONS OF PRISMS OVER SIMPLE 3-POLYTOPES [J].

ALSPACH, B ;

ROSENFELD, M .

GRAPHS AND COMBINATORICS, 1986, 2 (01) :1-8

[2]

ALSPACH B, 1980, C NUMER, V28, P217

[3]

ALSPACH B, 1984, DISCRETE MATH, V50, P115

[4]

Alspach B., 1985, Ann. Discrete Math, V27, P464

[5]

Alspach B., 1992, WIL INT S D, P13

[6]

Alspach B, 2015, ARS MATH CONTEMP, V8, P215

[7] Vertex-Transitive Graphs of Prime-Squared Order Are Hamilton-Decomposable [J].

Alspach, Brian ;

Bryant, Darryn ;

Kreher, Donald L. .

JOURNAL OF COMBINATORIAL DESIGNS, 2014, 22 (01) :12-25

[8]

[Anonymous], 1970, Combinatorial Structures and Their Applications

[9]

Babai L, 1979, SUMM RES WORKSH ALG

[10]

Babai L., 1995, Handbook of Combinatorics, V2, P1447

← 1 2 3 4 →