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

涂巧霞

(黄冈师范学院 数理学院，湖北 黄州 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 第个弱4-圈vivi-2vi+1vi+3vi(3≤i≤2k-3)是坏的.

结论2的证明

v2v5v7…v2k-1v2kv2k-2…v6v4

因此,v1v4∈A(D′).据结论1,当i=3时可得v5v2∈A(D′),当i=4时可得v3v6∈A(D′),类似地,当i=5,6,…,2k-2时,可以确定P2k中所有距离为3的弧.接下来考虑P2k中所有距离为2的弧,分两种情形:

情形1v3v1∈A(D′)

可以证明D′=A.只须证明v2v4∈A(D′)以及v5v3∈A(D′)即可,这是因为,据结论2,v3v1,v2v4,v5v3这三条弧可以确定P2k中所有距离为2的弧与A保持一致.

v3v6v8…v2kv2k-1v2k-3…v5v2

因此v2v4∈A(D′).

v1v4v6v8…v2kv2k-1v2k-3…v7v5

因此v5v3∈A(D′).

情形2v1v3∈A(D′)

与情形1同理可以验证,D=B.

定理5的证明: 只须证明充分性即可.不妨设D能推成强连通有向图,如果D不能推成哈密尔顿有向图,据引理7,则D要么推成A,要么推成B.据引理1和引理4,A和B均不能推成强连通有向图,那么D也不能推成强连通有向图,得到矛盾.

[1] Diestel R. Graph Theory[M]. New York :Spring-Verlag，2000.

[2] Klostermeyer W F， Solte L. Hamiltoncity and reversing arcs in Digraphs[J]. J Graph Theory,1998,28(1):13-30.

[3] 孙静,陈园,胡智全.关于一类立方图的可圈性研究[J].华中师范大学学报(自然科学版),2006,40(1):16-17.

[4] 涂巧霞.关于一类立方图的可连通性[J].大学数学,2009,25(6):100-103.

[5] Klostermeyer W F. An Analogue of Camion’s Theorem in Squares of Cycles[C]. Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics，1998，(132):205-218.

责任编辑 王菊平

A necessary and sufficient condition on the cube of path

TU Qiao-xia

(College of Mathematics and Physics, Huanggang Normal University, Huangzhou 438000, Hubei, China)

It is generally known that, Hamiltonian digraph must be strong connected digraph, on the contrary, it doesn′t work. This paper will prove that an orientation of the cube of a path with even order can be made strong using the push vertex operation， if and only if it can be made Hamiltonian using the push operation.

strong connected; Hamilton; push vertex

2017-03-04 doi 10.3969/j.issn.1003-8078.2017.03.05

涂巧霞，女，湖北武穴人，讲师，硕士，主要研究方向为运筹学与图论。

O157.5

A

1003-8078(2017)03-0025-03