涂巧霞

(黄冈师范学院 数理学院，湖北 黄州 438000)

关于路立方图的一个充要条件

涂巧霞

(黄冈师范学院 数理学院，湖北 黄州 438000)

在有向图中,哈密尔顿图一定是强连通图,但强连通图不一定是哈密尔顿图，本文证明了一类具有偶数阶的路立方图的任何定向,通过推点运算,可推成哈密尔顿有向图，当且仅当可推成强连通有向图.

强连通；哈密尔顿；推点

1 引言

文中未提及的符号和术语,参见[1].

关于路图的立方图的研究,主要有以下结果.

关于哈密尔顿可推性与强连通可推性的等价性,Klostermeyer已经证明如下结论.

定理4[5]圈图的平方图的任何定向,当且仅当可推成哈密尔顿图,一定可推成强连通有向图.

下文将定理4 的结果在路立方图上作一推广.

2 主要结果

图的定向A

图的定向B

引理1[4]A不能推成强连通有向图.

引理2R(A)能推成定向B.

证明 只须将R(A)中所有偶数标号的顶点集作推点运算即可.

引理3[5]定向D可推成强连通有向图(哈密尔顿有向图)当且仅当R(D)可推成强连通有向图(哈密尔顿有向图).

引理4B不能推成强连通有向图.

证明

反证法：若B能推成强连通有向图,则据引理3,R(B)也能推成强通有向图,由引理2,A能推成R(B),故A也能推成强连通有向图,与引理1矛盾.

引理5[2]若P是图G中的u-v路,则G的每个定向都可以通过推点运算,使P成为一条u-v有向路.

证明 设P2k=v1v2v3…v2k,若D不能推成哈密尔顿有向图,则据引理5,D可推成D′使得P2k成为一条有向v1-v2k路,以下可证D′∈{A,B}.首先验证两个结论:

结论1 每个弱4-圈vi-1vi-2vi+1vi+2vi-1(3≤i≤2k-2)是坏的.

结论1的证明

结论2 第……