一类一致最优完全多部图

以(n,m)表示具有n个顶点m条边的图的集合.假设图G的边可靠,而顶点可靠的独立概率为p,若对于所有1 p∈(0,1),图G均为(n,m)中的最可靠图,则称G为一致最优图.本文证明了完全k-部图K(b,(b+2)k 1)在其图类中是一致最优的,而当i>3时,完全k-部图K(b,(b+2)k 2,b+i)在其图类中不是一致最优的.     

广义Mycielskian图的连通度(英文)

Mycieski定义了一个图的运算即把一个图G变换为一个称为G的Mycielskian图的新图μ(G).广义Mycielskian图μm(G)(m≥0)是图的Mycielskian图的一个自然推广.本文证明对任意非平凡连通图G有κ(μm(G))=min{δ(G)+1,(m+1)κ(G)+1},而且对于m,i≥1,λ(μm(G))=λ(G)+i当且仅当δ(G)=λ(G)+i 1,其中κ(G),λ(G)和δ(G)分别为图G的连通度,边连通度和最小度.     

几类特殊图的优美性

证明了对任意大于1的自然数n,p,当m≥2p＋2时,非连通图Fm∪Kn,p和Fm,2 m∪Kn,p是优美图;当m≥3时,图Fm∪St（n）是优美图;当m≥4,图Fm,2 m∪St（n）和Fm,2 m∪Gr是优美图.     

图簇GS*(i)j1j2…jt(p,tkm)的伴随多项式的因式分解及色性分析

令S1,k表示k+1个顶点的星,Pm表示m个顶点的路,G是任意的p阶连通图.设V(Pm)={V1,V2,…,Vm-1,Vm}及相应的度序列为(1,2,…,2,1).SP(i)km+1表示把kPm的每个分支的第i个顶点Vi分别与星S1,k的k个1度点重迭后得到的图,用GS*(i)j1j2…jt(p,tkm)表示把tSP(i)km+1的每个分支的k度点分别与图G的顶点uj1,uj2,…,ujt(t≤p)重迭后得到的图,这里p≥1,k≥2,m≥3,1≤i≤m,t≥1.我们通过讨论图簇SP(i)km+1∪(k-1)K1、SP(i)2rm+1,SP(i)(2r-1)m+1以及GS*(i)j1j2…jt(p,2rmt),GS*(i)j1j2…jt(p,(2r-1)mt)的伴随多项式的因式分解,证明了它们的补图的色等价图的结构定理.推广了张秉儒证明的文[8]中的定理2和定理4.     

若干图的伴随分解及色等价性

设Pm和Cm分别表示具有m个顶点的路和圈,G是任意的r阶连通图,设m是正奇数,把路Pm的标号为奇数的2-1(m+1)个顶点分别与2-1(m+1)G每个分支的第i个顶点Vi重迭后所得到的图记为ρG(i)m+2-1(m+1)r。运用图的伴随多项式的性质,首先给出了一类图簇ρG(i)(2 m+2)+((m+1)r的伴随多项式。进而令m=2t-1 q-1,λn=(2nq-1)+2n-1 qr,在讨论上述图的伴随多项式的基础上,我们证明了图ρG(i)λt和ρG(i)λt∪(t-1)K1的伴随多项式的因式分解定理,进而证明了这些图类的补图的色等价性。     

两类E~G形图簇的补图的色等价性定理

设G是任意的p阶连通图,用ΨG(i)(k,p)表示把图G的第i个顶点vi与星图Sk+1的k度点重迭后得到的图(1≤i≤p),给出了图ΨG(i)(k,p)与星图Sn+1组合而成的两类EG形图簇,并通过研究这些图簇的伴随多项式的因式分解,进而证明了它们的补图的色等价性定理。     

2-连通P3-支配图的哈密尔顿性

设G是n阶2-连通P3-支配图,我们证明了如果δ≥n/4,则G是哈密尔顿的或G∈F ∪{K2,3,K1,1,3},这里F是一类已知的2-连通非哈密尔顿图.     

一类(0,1)矩阵变换图的Hamilton性

设G(R,S)表示m×n阶(0,1)矩阵类(R,S)的变换图.Brualdi提出问题:“G(R,S)有Hamilton圈吗?”当min{m,n}=2时,文献[3]中证明了此变换图是Hamilton连通的,并且是泛圈的(除K_1,K_2外),从而给该问题一个肯定的答案,当min{m,n}=3时,本文进一步地证明了此变换图是边Hamilton的(除K_1,K_2外),从而也给出该问题一个肯定的答案。     

关于图的边着色的一个猜想

若G是简单图,v(G)是偶数,χ'(G)=?(G)+1,则存在点v∈V(G),使χ'(G-v)=χ'(G)=?(G)+1.本文对此进行了研究,当图G满足以下条件之一时:(1)设G是含有割边的连通图,χ'(G)=?(G)+1;(2)设G是连通图,κ'(G)=2,G中最多除两个2度顶点外,其它顶点的度数均为k(k2),v(G)=2n+2,χ'(G)=?(G)+1;(3)设图G是k正则图,v(G)=2n+2,χ'(G)=?(G)+1;(4)设图G是有2n+2个顶点的连通图,且除点v的度小于k外,其它顶点的度都等于k,χ'(G)=?(G)+1;(5)设图G是有2n+2个顶点的连通图,且除点u,v,d(v)d(u)k外,其它顶点的度都等于k,χ'(G)=?(G)+1;此猜想也是成立的.     

冠图G1. Km1,m2的邻接谱

给定简单图G1和G2,G1的顶点标记为v1,v2………,vn1.图G1和G2的冠图G1.G2被定义为取n1个G2的拷贝,然后连接vi与相应的G2的第i个拷贝中的每一个点(i=1,2………,n1)所得到的图.在文献[2]中,对连通图G1和任一正则图G2,S.Barik,S.Pati和B.K.Sarma给出了G1.G2的邻接谱的完整的表达式.继文献[2]的工作进一步考虑当G2是非正则图时冠图G1.G2的邻接谱.本文完全确定了冠图G1.Km1,m2的邻接谱,其中Km1,m2是完全二部图.