立方图的可圈性

Cyclable cube of a graph

图的可圈性是哈密尔顿性的一个推广.设G是有向图,如果对G的每一个定向D,都存在S(D)V(G)使在D中改变所有恰与S(D)中一个顶点相关联的弧的方向后所得到的图为有向哈密尔顿图,则称G为可圈图.证明至少含5个顶点的连通图G的立方图是可圈图当且仅当G不同构于任何一条偶路.该结果改进了Klostermeyer的3个定理.

The cyclability of graphs is a generalization of Hamiltonian. A graph G is said to be cyelable if for each orientation D of G, there exits a set S（D）íV（G） such that revising all the arcs with one end in S results in a Hamiltonian digraph. Show that the cube of a connected graph with at least five vertices is cyclable if and only if this graph is not isomorphic to any even path. This improves these results of Klostermeyer et al.