114—三次图的构造

在[1]中,只讨论了不含三角形时abc为111和222两种情况的abc—三次图,本文的目的是解决114—三次图的存在问题,并且给出一个图是114—三次图的充要条件,它类似于[1]中的定理4,但不必给予“无三角形”的限制。我们用G表示一个连通的无自环的非K_4的三次图,H表示G的一个最大二部分子图,H中的一条路如果满足(ⅰ)非平凡(ⅱ)它的端点在H中为3度(ⅲ)所有其它顶点在H中为2度,则称这样的一条路为H的一条初等路。如果G的最大二部分子图日中每个3度顶点是长度分别为a、b、c的三条初等路的公共端点,则称G为abc—三次图,若S是G的顶点集V(G)的一个子集,则K=[S,]表示G的棱集E(G)的一个子集,它的端点一个在S中,另一个在中,且称K为G的棱截。截指标c(K,H)定义为:     

115—三次图的结构和124—三次图的存在唯一性定理

对abc—三次图的存在定理与某些特殊图类的结构,[1]、[2]、[3]中已作了一些讨论,本文的目的是讨论其中未解决的115—三次图和124—三次图的结构。所用概念与记号均与[1]、[2]、[3]相同,其它概念和记号见[4],所有图中的实线表示E(L)中的棱,虚线表示E(G)—E(L)中的棱。一、115—三次图的结构引理1 设G是一个115—三次图,L是它的最大二部分子图,则L中任一长为5的初等路必定含在L的一个6回中。     

论abc—三次图

G.Malle在《论最大二部分子图》一文中提出了关于abc—三次图的一些问题,他指出了111—三次图是连通二部分三次图,并证明了不含三角形的图是222—三次图的充要条件是图为彼得松图或十二面体图,他还指出,对其它abc—三次图的特征是尚未解决的问题。本文解决了在“无三角形”限制下abc—三次图的存在性及最小图,以及不加任何限制的abc—三次图的存在性及最小图。本文及我们的[5][6][7]三文基本上解决了G.Malle提出的问题,同时也证实了他关于“可能某些abc—三次图不存在”的说法, 一、无三角形abc—三次图的存在性及最小图本文使用[1]及[2]的有关术语及记号。图G的子图H称为G的最大二部分子图,若对G的任意二部分子图H′,都有ε(H′)≤ε(H),这里ε表示图的棱数。     

与图的中心有关的两个定理

本文讨论与图的中心有关的问题。使用的一般术语与记号与[1]相同。图G中两顶点x与y之间的距离用d_G(x,y)表示,x的联系数(eccentricity)e_G(x)=(?) d_G(x,y)。G的半径与直径分别记为r(G)=(?) e_G(x)与d(G)=(?) e_G(x)。G中以r(G)为联系数的顶点叫做G的中心点,全体中心点集的诱导子图叫做G的中心,记为c(G)。满足c(G)=G的图G叫做自中心图。首先,我们讨论以任意的图H作为中心的图G的直径与半径之间应满足的关系。     

冠图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是完全二部图.     

二面体群的双凯莱图的匹配可扩性（英文）

令G为有限群,S为G的非空有限子集,G关于S的双凯莱图BC(G,S)是一个二部图,其顶点集是G×{0,1},边集是{(g,0)(sg,1)|g∈G,s∈S}.若有完美匹配的连通图Γ至少有2n+2个顶点,且每一个大小为n的匹配都可以扩充为一个完美匹配,则称此完美匹配的连通图Γ是n-可扩的,并对二面体群的双凯莱的2-可扩性进行了刻画.     

二面体群的双凯莱图的匹配可扩性

令G为有限群,S为G的非空有限子集，G关于S的双凯莱图BC(G,S)是一个二部图,其顶点集是G×{0,1},边集是{(g,0)(sg,1)|g∈G,s∈S}.若有完美匹配的连通图Γ至少有2n+2个顶点,且每一个大小为n的匹配都可以扩充为一个完美匹配，则称此完美匹配的连通图Γ是n 可扩的,并对二面体群的双凯莱的2 可扩性进行了刻画.     

关于3-连通图最长圈的注

设C是3-连通图G的一个最长圈,H是G-V(C)的一个分支满足|H|≥3.文献[4]在给H附加一些条件后,证明|C|≥2d(u) 2d(v)-5,并且不等式严格成立除非G属于某些例外图类,这里u,v是G中两个不相邻的顶点.本文给出了上述例外图类的精确刻划.     

一类一致最优完全多部图

以(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)在其图类中不是一致最优的.     

路图P3(G)的色数

设G是一个图,G的路图P3(G)的顶点集是G中所有三个顶点的路P3, 当G中的两个P3路形成P4路或C3圈时,在P3(G)中它们所代表的两个顶点相邻. 在这篇文章中,我们得到对于一个无三角形的图G, χ(P3(G))≤β(G),其中β(G)表G的点覆盖数. 对于顶点数至少为3的连通图G,χ(P3(G))≤2当且仅当G是二部图, 并且χ(P3(G))=1当且仅当 G是星图. 对于K4的剖分图G,2≤χ(P3(G))≤3. 对于系列平行图和外可平面图G,χ(P3(G))≤3.     

图簇Gj1j2…jt^S^＊（i）（p,tkm）的伴随多项式的因式分解及色性分析

令S1，k表示k＋1个顶点的星，Pm表示m个顶点的路，G是任意的p阶连通图，设V（Pm）={V1，V2，…，Vm-1，Vm}及相应的度序列为（1，2，…，2，1）。S2km＋1^p（i）表示把kPm的每个分支的第i个顶点Vi分别与星S1,k的k个1度点重迭后得到的图，用Gj1j2…ji^S^＊（i）（p，tkm）表示把tSkm＋1^P（i）的每个分支的k度点分别与图G的顶点uj1，uj2，ujt，ujl（t≤p）重迭后得到的图，这里p≥1，k≥2，m≥3，1≤i≤m，t≥1．我们通过讨论图簇Skm＋1^p（i）,U（k-1）K1、S2rm＋1^P（i），S（2r-1）m＋1^P（i）以及Gj1j2…jt^S＊（i）（p，2rmt），Gj1j2……jt^S＊（i）（2r-1）mt）的伴随多项式的因式分解，证明了它们的补图的色等价图的结构定理，推广了张秉儒证明的文[8]中的定理2和定理4。     

复合图点列表着色的可选性

r部完全图Km*r是完全图Kr与空图Sm的复合图Kr[Sm] . Erdo。s P, Rubin A L和Taylor H在[1]提到了确定Kr[Sm]的点列表着色的可选性的问题并证明了ch(Kr[S2]) = r .Kierstead H A[2]证明了ch(Kr[S3]) =[(4r - 1)/3] .假定Gm是圈Cn与空图Sm的复合图Cn[Sm] .考虑了Gm的列表着色的可选性并证明了ch(G2) =3, ch(G3)≤ 4及在n是奇数时, ch(G3) = 4 .     

Cartesian积与邻点可区别着色之间的关系（英文）

图G的一个正常k-边着色是指k种颜色1,2,…,k对图G各边的一个分配,使得任意2条相邻边染以不同的颜色.对于图G的一个正常边染色f和G中任何一个顶点x,Sf(x)或S(x)表示与顶点x关联的边在f下的颜色所构成的集合.若对于图G中任意2个相邻顶点u和v,有S(u)≠S(v),则称f为图G的邻点可区别正常边染色.对图G进行邻点可区别正常边染色所需的最少颜色数,称为G的邻点可区别正常边色数,记为χ′a(G).图G的一个正常k-全染色是指k种颜色对图G的顶点和边的一个分配,使得任意2个相邻的或相关联元素染以不同的颜色.对于图G的一个正常全染色g和G中任何一个顶点x,使用Cg(x)或C(x)来表示顶点x的颜色(在g下)以及与顶点x关联的边在g下的颜色所构成的集合.若对于G中任意2个相邻顶点u和v,有C(u)≠C(v),则称g为图G的邻点可区别全染色.图G的邻点可区别全染色所需的最少颜色数称为图G的邻点可区别正常全色数,记为χ″a(G).主要讨论了Cartesian积和2种邻点可区别染色之间的关系.     

关于4—正则图的Berge猜想

我们用G=(V,E)表示简单4—正则图,v(G),ε(G)分别表示G的顶点数及棱数,即λ_(G)表示G的圈棱连通度(Cyclic edge Connectivity),λ_(G)=Min{|E′||E′E,G—E′仅由两个均含有回的连通分支构成}。若满足上述条件的E′不存在,则规定λ_(G)=ε(G)。本文中未加说明的其他记号及术语均见[1]。     

Able群上Cayley图的哈密顿性

设G是群，S是G的不含单位元的子集，满足S＝S^1，G的相对于S的Cayley图，是一个以G为顶点集的无向图，对G的任意两上元x和y,x和y在C（G，S）中相邻，当且今当x^2y∈S，本文中我们得到了以下结论：（1）设G是阶至少为2的有限Abel群，S真包含于G\{0}且S＝S^1，则C（G，S）中每个二长路都包含在一个哈密顿圈中。（2）设G是可数无限Abel群，S真包含于G\{0}满足S＝S^1和|S|≥4。则C（G，S）中每个长为2的路含有一条双向哈密顿路上。（3）有限Able群上围长为3，阶数至少为3的连通Cayley图是泛圈的。（4）设G是可数无限Able群，S真包含于G\{0}满足S＝S^1和|S|≥，若girth[C(G,S)]=3,则C（G，S）是泛圈的。     

一些特殊图类乘积的离散度

连通图的离散度是用s(G)来表示的,s(G)=max{ω(G-S)-|S|:ω(G-S)>1,SV(G)}.给出了两个完全图乘积的和一个完全图与路的乘积的离散度.还给出了两个完全图乘积的坚韧度.     

Cartesian积与邻点可区别着色之间的关系

图G的一个正常k-边着色是指k种颜色1,2,…,k对图G各边的一个分配,使得任意2条相邻边染以不同的颜色.对于图G的一个正常边染色f和G中任何一个顶点x,S_f（x）或S（x）表示与顶点x关联的边在f下的颜色所构成的集合.若对于图G中任意2个相邻顶点u和v,有S（u）≠S（v）,则称f为图G的邻点可区别正常边染色.对图G进行邻点可区别正常边染色所需的最少颜色数,称为G的邻点可区别正常边色数,记为χ'_a（G）.图G的一个正常k-全染色是指k种颜色对图G的顶点和边的一个分配,使得任意2个相邻的或相关联元素染以不同的颜色.对于图G的一个正常全染色g和G中任何一个顶点 x,使用C_g（x）或C（x）来表示顶点x的颜色（在g下）以及与顶点x关联的边在g下的颜色所构成的集合.若对于G中任意2个相邻顶点u和v,有C（u）≠C（v）,则称g为图G的邻点可区别全染色.图G的邻点可区别全染色所需的最少颜色数称为图G的邻点可区别正常全色数,记为χ″_a（G）.主要讨论了Cartesian积和2种邻点可区别染色之间的关系.     

图簇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.     

关于图的直径的一个定理

学生习作本文主要讨论[1]中P197页定理10.9。这个定理是:“If G and ■ are Connected, then d(G) d(■)≤P 1”。定理中的G是p个顶点的图,■是G的补图。d(G),d(■)分别表示G和■的直径,即图的顶点的最大偏心度。该书对此定理未加证明,且在叙述了该定理后又说:“The bound is always attain.     

双图的一些脆弱性参数

一个图G的双图（double graphs）的定义为D[G]=G×T2,这里×表示图的直积,而死表示两个顶点的全图．本文研究了图的双图的一些脆弱性参数．