论文部分内容阅读
本文对非完全覆盖图的重构进行了研究。主要内容如下:
⑴令Γ=(V(Γ),E(Γ))表示一个以V(Γ)为点集,E(Γ)为边集的有限非空无向图。对于任意一个非负整数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(Γ)简记为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(Γ)允许一个非平凡的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)和σ∈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的情形.完成这个工作需要研究度数为4或7的(X,2)-弧-传递图.基于[3]中的结果,我们将在第一章给出4度(X,2)-弧-传递图的一个划分;同时我们将证明任何一个4度的(X,2)-弧-传递的非完全图都是准n边形,这里n≥4是一个整数.对于7度的(X,2)-弧-传递图∑,我们将证明∑可以作为一个满足条件的Γ的商图,当且仅当Xr∑(τ)≌PSL(3,2),这里τ∈V(∑)。
⑶对于任意一个X-对称图∑,我们将给出存在一个(X,s)-弧-传递图Γ以∑为商图,且Γ不是∑的完全覆盖图的充要条件。同时,当这一条件满足时,我们将给出一个方法来构造这样一个Γ;进一步地,对于任何一个(X,s)-弧-传递图Γ,这里s≥1,我们可以从∑出发,经过m(1m是一个自然数)次这样的构造过程,我们将得到一个图ΓBm,使得Γ≌ΓBm或者Γ是ΓBm的一个完全覆盖。