關于路立方圖的一個充要條件

涂巧霞

(黃岡師范學院 數理學院，湖北 黃州 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