Gray code numbers for graphs

被引：15

作者：

Choo, Kelly ^{[1
]}

MacGillivray, Gary ^{[1
]}

机构：

[1] Univ Victoria, Victoria, BC V8W 3R4, Canada

来源：

ARS MATHEMATICA CONTEMPORANEA | 2011年 / 4卷 / 01期

关键词：

Graph colouring; cyclic Gray code;

D O I：

10.26493/1855-3974.196.0df

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A graph H has a Gray code of k-colourings if it is possible to list all of its k-colourings in such a way that consecutive elements in the list differ in the colour of exactly one vertex. We prove that for any graph H, there is a least integer k(0)(H) such that H has a Gray code of k-colourings whenever k >= k(0)(H). We then determine k(0)(H) whenever H is a complete graph, tree, or cycle.

引用

页码：125 / 139

页数：15

共 16 条

[1]

[Anonymous], 1989, COMBINATORIAL ALGORI

[2]

Bondy J. A., 1976, Graduate Texts in Mathematics, V290

[3]

Bonsma P., 2007, ELECT NOTES DISCRETE, V29, P463

[4]

Cereceda L., J GRAPH THE IN PRESS