该结果由徐俊明, 徐克力所证明.

References
徐俊明, 徐克力. Cayley 图的笛卡尔乘积, 中国科学技术大学学报 Vol.31, No.6, Dec. 2001, 635--640.

假设 $\Gamma$ 是一个非平凡有限群, $S$ 是 $\Gamma$ 的非空子集, 且不含单位元. 定义一个有向图 $G$ 如下:

\[ V(G)=\Gamma;\quad (x,y)\in E(G)\Leftrightarrow x^{-1}y\in S,\ \forall\ x,y\in\Gamma. \]

称 $G$ 为群 $\Gamma$ 关于子集 $S$ 的 Cayley 图, 记为 $C_\Gamma(S)$.

假设 $G_i=(V_i,E_i),\ i=1,2,\ldots,n$ 是 $n$ 个图, 它们的笛卡尔乘积 $G=G_1\times G_2\times\cdots\times G_n$ 定义为, $V(G)=V_1\times V_2\times\cdots\times V_n$, 且 顶点 $(x_1,x_2,\ldots,x_n)$ 与 $(y_1,y_2,\ldots,y_n)$ 之间存在一条边当且仅当这两个顶点(向量)的坐标仅有一个分量是不同的, 比如 $x_{i_0}\neq y_{i_0}$, 并且 $(x_{i_0},y_{i_0})\in E_{i_0}$.

http://www.math.uiuc.edu/~west/openp/cqhamwt.html

 

Zhang's Hamiltonian Weight Conjecture

Originator(s): Cun-Quan Zhang, West Virginia University

Conjecture/Question: Every 3-connected 3-regular graph having a Hamiltonian weight arises from K₄ by a sequence of Delta-Wye operations.

Definitions/Background/motivation: A Hamiltonian weight on G is a map f from E(G) to {1,2} such that every family of cycles that covers each edge e exactly f(e) times consists of two Hamiltonian cycles. A Delta-Wye operation replaces a triangle in a 3-regular graph with a single vertex incident to the three edges that emanated from the triangle.

The study of Hamiltonian weights is motivated by the cycle double cover conjecture of Szekeres and Seymour and by the unique edge-3-coloring conjecture of Fiorini and Wilson.

Partial results: The conjecture was proved in [1] for those graphs not having the Petersen graph as a minor.

References:
[1] Lai, Hong-Jian; Zhang, Cun-Quan. Hamilton weights and Petersen minors. J. Graph Theory 38 (2001), no. 4, 197--219; MR2002g:05120 05C45 (05C70)

 

希伍德(Heawood)的猜想