论文部分内容阅读
设G是无向简单图，定义Gk为G的k次幂，其顶点集V(Gk)=V(G)，边集E(Gk)={uv|dG(u，v)≤k，u，v∈V(G)}。设D是一有向图，如果D中存在有向圈C含D中所有顶点，则称C为D的哈密尔顿有向圈。如果D中含有一个哈密尔顿有向圈，则称D为哈密尔顿有向图。若对有向图D中任意两个不同顶点x，y，D中既存在从x到y的有向路，又存在从y到x的有向路，则称D为强连通有向图.在有向图D中，定义推点v为将D中所有与v关联的弧反向.若一同构于H的有向图可通过对有向图D施行一系列推点运算得到，则称D可推为H.若某简单图的所有定向均可推成哈密尔顿有向图，则称其为可圈图。
Camion的一个著名定理宣称一个竞赛图是强连通有向图当且仅当其为哈密尔顿有向图。Klostermeyer证明了圈平方的任意一个定向可推成强连通有向图当且仅当其可推成哈密尔顿有向图。在本文中，我们将证明路的三次方的任意一个定向可推成强连通有向图当且仅当其可推成哈密尔顿有向图。作为推论，当n≥4和n=偶数时，阶为n的路的三次方的23n6-个定向中存在23n-6 -2n个定向可推成哈密尔顿有向图(从而可推成强连通有向图)。