133—三次图的结构

在[1]中引入了abc—三次图的概念,但仅讨论了两类特殊abc—三次图的结构,本文的目的是解决133一三次图的结构问题。我们用G表示一个连通、无自环、非K_4的三次图,L表示G的最大二部分子图,若S是G的顶点集V(G)的一个子集,则K=[S,]表示G的一个棱截,截指标c(K,L)定义为: c(K,L)=|K∩L|-|K-L|=|L|-|KL|,其中“”表示对称差。本文引用的其它概念与记号见[1]、[2]、[3]。为了叙述方便,我们将133—三次图G的最大二部分子图L的顶点分划集X、Y以两种不同的染色,两个顶点不同色即指它们分属L的不同顶点分划集合。     

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)定义为:     

论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),这里ε表示图的棱数。     

关于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]。     

关于临界h棱连通图的最大棱数及最大图的结构(Ⅱ)——临界h棱连通图的性质和最大临界3棱连通图类的刻划

设λ(G)表示G的棱连通度,图G称为临界h棱连通的,如果λ(G)=h而且对任何x∈V(G),λ(G-x)≤h-1,具有最大棱数的临界h棱连通图称为最大临界h棱连通图.本文首先证明对h≥3的临界h棱连通图的若干性质,然后证明最大临界3棱连通图的每个顶点都与3度点相邻,并由此给出了此类图的结构刻划和最大棱数.     

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

本文讨论与图的中心有关的问题。使用的一般术语与记号与[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的直径与半径之间应满足的关系。     

连通图顶点集的一种划分

1.引言设G=(X,E)为有限阶的简单图,X与E分别为G的顶点集与棱集。在下文中,我们总假定G是连通的。以d(x,y)表示G的两个顶点x,y之间的距离。对于每个x∈X,定义x的“联系数”(associated number)为     

n—补树图及其性质

补数图是为了研究特殊的R L电路网络结构而引入的,它的定义如下:设G是连通图,若存在两棵生成树T_1和T_2,且满足G=T_1UT_2,T_1 ∩T_2=φ,则称G是补树图,或称G具有补树结构。对这种图的性质,已有人作了一些讨论。本文的目的在于_2将补树图的概念推广到n-补树图,并讨论它的一系列性质。这样,[1]中定义的补树图即为本文定义的n-补树图的一个特例-2-补树图,而[2]中所论的补树图的一些性质也成为本文讨论的n-补树图的性质的直接推论。     

列表双临界图（英文）

G是k-可着色的连通图,如果对于G中的所有边uv,都有G-u-v是(k-2)-可着色的,则称图G是双临界图.由Erdo?s和Lova′sz提出了一个长期未能解决的猜想:完全图是唯一的双临界图[1].连通图G称为边双临界图,如果G中包含多对不相邻的边,并且对于任意一对不相邻的边e1,e2,都有χ(G-e1-e2)=χ(G)-2,其中χ(G)表示图G的色数.Kawarabayashi等人[2]及后来的Lattanzio[3]证明了完全图是唯一的边双临界图.文章证明了在图G中,对于任意的两个点u,v∈V(G),如果ch(G-u-v)=ch(G)-2,则图G是完全图,其中ch(G)表示G的选择数,还证明了完全图是唯一的列表双临界图.     

极小2—棱—连通图的周长

图中最长的初等回(elementary cycle)的长度,称为图的周长,关于图的周长的问题,是图论中较困难的问题之一。在本文中,我们利用[2]中所得到的关于极小2—棱—连通图的一些性质,给出了依赖于图的阶和棱数的上界和下界,在一定的意义下,本文所获得的结果是最好的。     

关于图的直径的一个定理

学生习作本文主要讨论[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 是简单图.A(G)是 G 的邻接矩阵,A(G)是非负的对称阵,其特征根全是实数,故必有最大特征根.文献[2]中讨论了图的最大特征根(以下简称大根)的某些变化规律,进行了这方面的研究.本文将继续讨论图的大根问题.主要结果是:1、给出图的大根变化规律的一个一般性定理.此定理类似于文献[3]的定理.运用它可以推广文献[2]中结果到更一般的情形.2、给出一个以一定方式联出某些子图而构成的图类的大根变化规律.     

无割边三正则图三边着色的一个充分必要条件

设G是无割边三正则图，θ={C1，C2，…，Ck)是G一个圈覆盖，定义一新图G(θ)=(V，E)，这里V={C1，C2，…,Ck)，(Ci，Cj)∈E当且仅当E(Ci)∩E(Cj)≠φ(1≤i≠j≤k)．那么G是三边着色的充分必要条件是G有一个圈的一或二次覆盖θ并且G(θ)是二或三点着色．这个结论给出了一个判定无割边三正则图是三边着色的方法。     

基回数为2的自中心图

Buckley 指出找寻自中心图的特征是一个困难的任务.作为这一工作的开始,找出一些自中心图类看来非常必要.文[1]定理3中证明当 k=■或 n≤k≤[(1/2)n(n-1)]时,n 个顶点 k 条边的自中心图存在.本文建议以基回数为出发点构造自中心图,并确定了基回数为2,即 k-n=1的全部自中心图.本文还纠正了[1]中的一个疏忽.设 G=(V,E)是简单图,u,v∈V(G),d(u,v)为 u,v,两点的距离.定义1 图 G 的半径 r(G)=(_{(v,w)}定义2 图 G 中顶点“的最远距离     

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

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 .     

Banach空间中(E_1)拓扑的完备性问题

1 引言和记号 (E_1)拓扑概念,首先见于[1].由于此拓扑弱于范数拓扑(Mackey拓扑(?)(E,E′))而又强于弱拓扑σ(E,E′)因而颇有趣。在(E_1)拓扑下完备性问题,文[2]讨论了列完备的情况,但在一般情况下列充备与有界完备概念是不同的,后者蕴含前者,后者需用网或滤子为收敛工具进行讨论,本文利用滤子讨论(E_1)拓扑的有界完备性问题。     

几类优美图

设图G=(V(G),E(G))是一个简单图,V(G)是G的所有顶点的集合,E(G)是G的所有边的集合。若存在从V(G)到集合{0,1,…,ε}(ε=|E(G)|)的一个单射φ,对u,v∈V(G),(u,v)∈E(G),导出集合{|φ(u)-φ(v)|}到集合{1,2,…,ε}的一个一一映射,则称φ是图G的一个优美标号。若图G有一个优美标号φ,则称图G是优美图。我们依照文献[1]的定义称图G是G_1和G_2的联,如果图G是由G_1∪G_2和所有联接V(G_1)和V(G_2)的线组成的图。记为G=G_1+G_2。例如一个完全二部分图就是两个孤立点集S_1和S_2的联。我们知道这是优美图。     

欧拉环游图的边哈密顿性

设G是一个无自环的欧拉多重图,E是G的一个欧拉环游,对任意的v∈V(G),deg v=2t,E通过V顶点的次数恰等于t。我们可以将E表示为:e_0ve_1…e_2ve_3…e_ive_(i+1)…e_(2-2)ve_(2)-1)…e_。三元组(e_i,v,e_(i+1))被称为过顶点v的一个转移。因为G是无向图,三元组(e_i,v,e_(i+1))和(e_(i+1),v,e_i)表示同一个转移,两个方向相反的欧拉环游被当作同一个欧拉环游。以v为起点和终点的E的一个真子序列被称为E的一个v—v段。将E的某一v—v段S改换方向可以得到G的另一欧拉环游F。E和F之间的这种变换被称为在S段上的K—变换。     

双广义Petersen图的可靠性分析（英文）

设G是连通图,图G的超连通度(超边连通度)是指从图G中删除最小数目的点(边)使得G不连通,且在G的每个分支中不存在孤立点.周进鑫和冯衍全(2012)首次提出了双广义Petersen图的概念,文章证明了双广义Petersen图DP[n,k]是超连通和超边连通的,以及当n?{2k,3}时,κ_1(DP[n,k])=λ_1(DP[n,k])=4.     

再论q^—图

本文在文[1]的基础上,讨论了没有q-割团、但有(q+1)-割团且q-色唯一的q-图的结构。