關于非完全覆蓋圖的重構.pdf

1、本文對非完全覆蓋圖的重構進行了研究。主要內容如下：
　　 ⑴令Γ=(V(Γ)，E(Γ))表示一個以V(Γ)為點集，E(Γ)為邊集的有限非空無向圖。對于任意一個非負整數(shù)s及V(Γ)上的一個s+1-序列α=(α0，…，α8)，α稱為Γ上的一條s-弧，如果{αi，αi+1)∈E(Γ)，對于i=0，1，…，s-1，并且αi-1≠αi+1，對于i=1，2，…，s-1.記Arc8(Γ)為Γ上所有s-弧的集合。通常，我們將1-arc和Arc1

2、(Γ)簡記為arc和Arc(Γ)。令X表示作用在V(Γ)上的一個有限群，使得對于任意的x∈X，E(Γ)x=E(Γ)(即X保持Γ的鄰接關系).Γ稱為X-點傳遞的，如果X在V(Γ)上的作用是傳遞的(即對于任意的αi，αj，∈V(Γ)，存在x∈X滿足αix=αj)。一個點傳遞圖Γ稱為是(X，s)-弧-傳遞的，如果X在Arcs(Γ)上誘導的作用是傳遞的.(X，1)-弧-傳遞圖又稱為X-對稱圖.
　　 ⑵稱Γ是X-非本原圖，如果V(Γ)允

3、許一個非平凡的X-不變的劃分召，也就是一個劃分B，使得對于任意的B∈B及x∈X，有1<｜B｜<｜V(Γ)｜且Bx∈B.此時我們可以定義Γ關于劃分B的商圖ΓB為以B為點集的一個圖，其鄰接關系為：對于任意的B，C∈B，{B，C)∈E(ΓB)當且僅當存Γ中的兩個點σ∈B和τ∈C使得{σ，τ}∈E(Γ).我們考慮ΓB不是空圖的情形，此時由[1]我們有對于任意的B∈B，B是Γ的一個獨立集。稱Γ是ΓB的多重覆蓋圖，如果對于任意的{B，C}∈E(ΓB

4、)和σ∈B，存在τ∈C使得{σ，τ]∈E(Γ)，否則稱Γ不是ΓB的多重覆蓋圖.特別地，如果上述τ是唯一存在的，就稱Γ是ΓB的覆蓋。當Γ是一個有限非空的(X，2)-弧-傳遞圖，B為其上一個非平凡的X-不變的劃分，使得ΓB非空且Γ不是ΓB的多重覆蓋圖時，文獻[2]給出了(Γ，X，B)當｜Γ(C)∩B｜=2時的一個刻畫，這里B∈B且C∈ΓB(B).這個結果促使我們研究當｜Γ(C)∩B｜=3的情形.完成這個工作需要研究度數(shù)為4或7的(X，2)-

5、弧-傳遞圖.基于[3]中的結果，我們將在第一章給出4度(X，2)-弧-傳遞圖的一個劃分；同時我們將證明任何一個4度的(X，2)－弧－傳遞的非完全圖都是準n邊形，這里n≥4是一個整數(shù).對于7度的(X，2)-弧-傳遞圖∑，我們將證明∑可以作為一個滿足條件的Γ的商圖，當且僅當Xr∑(τ)≌PSL(3，2)，這里τ∈V(∑)。
　　 ⑶對于任意一個X-對稱圖∑，我們將給出存在一個(X，s)-弧-傳遞圖Γ以∑為商圖，且Γ不是∑的完全覆蓋圖