关于一类立方图的可圈性研究

On the cyclability of some cube graphs

设G为无向图,如果对G的每一个定向D,都存在S(D)V(G)使在D中改变所有恰与S(D)中一个顶点相关联的弧的方向后所得的图为有向哈密尔顿图,则称G为可圈图.K losterm eyer和So ltes证明了P34k(k≥1)是不可圈图,现证明对任意整数n≥3,P3n是可圈图当且仅当n为奇数.

A graph G is said to be cyclable if for each orientation D of G, there exists a set S（D）compriseV（G） such that reversing all the arcs with one end in S results in a Hamilton digraph. Klostermeyer and Soltes have proved that P4k^3（k≥1） is not cyclable. It shows that for any integer n≥3, Pn^3 is a cyclable graph if and only if n is odd.