關于一類圖的可圈性與強連通可推性.pdf

1、設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(tǒng)的有向路，又存在從y到x的有向路，則稱D為強連通有向圖.在有向圖D中，定義推點v為將D中所有與v關聯(lián)的弧反向.若一

2、同構于H的有向圖可通過對有向圖D施行一系列推點運算得到，則稱D可推為H.若某簡單圖的所有定向均可推成哈密爾頓有向圖，則稱其為可圈圖。 Camion的一個著名定理宣稱一個競賽圖是強連通有向圖當且僅當其為哈密爾頓有向圖。Klostermeyer證明了圈平方的任意一個定向可推成強連通有向圖當且僅當其可推成哈密爾頓有向圖。在本文中，我們將證明路的三次方的任意一個定向可推成強連通有向圖當且僅當其可推成哈密爾頓有向圖。作為推論，當n≥4和n