二面体群上的Hamilton图

摘要

令Ｇ是一个有限群，Ｓ是Ｇ的一个生成元集，定义Ｇ上的Ｃａｙｌｅｙ图为Г＝Г（ＧＳ），其中顶，久集为Ｖ（Г）＝Ｇ，边集为Ｅ（Г）＝｛（ａ，ｂ）｜ａ，ｂ∈Ｇ，ａ（－１）ｂ∈Ｓ｝，令Ｄｎ表示２ｎ阶的二面体群，Ｓ＝Ｓ（－１）是Ｄｎ的生成元集。本文证明了Ｄｎ上的Ｃａｙｌｅｙ图Г（Ｄｎ，Ｓ）具有Ｈａｍｉｌｔｏｎ圈。从而证明了Ｗ．Ｈｏｌｓｚｔｙｎｓｋｉ和Ｒ，Ｆ，Ｅ，Ｓｔｒｕｂｅ猜想［１］。