悬图重构的两个新结果

图的重构问题是图论中的著名难题。设G是一个p点图,G_1,G_2,…,G_p是G的p个主子图,重构猜想说:G可由G_1,G_2,…,G_p唯一决定(至多差一个同构)。由于一般重构猜想极难解决,所以许多工作都限于证明一些特殊的图类是可以唯一重构的。     

图和补图线荫度的关系

定义1对简单图G(V,E),E的分划}普1‘·’‘“,+·““‘,‘”·E一UE,, 讼一t使得E,的导出图G[E;](i一l,2,不含圈的最小n,称为‘的线荫度,。‘(G). 定理1若‘是外平面图,则 a‘(G)成2. 定理2对简单图G(V,E),且下界不可改进.其中P一}V(G).,「x1为不小于x的最小整数.…,,)简记作图和补图线荫度的关系@张忠辅$兰州铁道学院 @王建方$中国科学院应用数学研究所!北京 @徐登洲$西北师范大学~~     

1坚韧图的Hamilton性

设G是一个图,且t是一个实数,若对每个,其中k(G—S)是G—S的分支数,则称G是t坚韧图(t-tough graph)。显然,1坚韧图是2连通的。用δ,κ,α分别表示G的最小度、连通度和独立数,利用以上记号,有如下定理: 定理1 设G是p阶1坚韧图,若δ≥     

关于唯一泛圈的图

所谓唯一泛圈的图(简称UPC图)G是指一个简单图,对每一个l,3≤l≤v,它恰有一个长为l的圈。确定所有UPC图是一个尚未解决的问题(见文献[1],p247)。至今知道的UPC图只有七个,它们是K_3,C_5 e,G_8~((1)),G_8~((2)),G_(14)~((1)),G_(14)~((2))和G_(14)~((3))(见图1)。我们约定本文讨论的图都是恰含一个Hamilton圈的简单图,所用术语和记号凡未加定义的均采自文献[1]。     

关于两类图的色多项式

目前,只有为数很少的几类图有色多项式的计算公式,而对绝大多数图而言,计算色多项式仍是非常不方便的。本文为两大类图找到了色多项式的计算公式,并为寻找更多的色多项式的计算公式提供了一定的模式。这两大类图是:一条长为n的路P_n的补图(?)_n以及n圈的补图(?)_n。     

无爪图中圈的弦的最大数目

本文讨论无向简单图。设C=v_1v_2…v_mv_1是图G的一个圈,G的边v_iv_i称为C的一条弦,如果i(?)j±1(其中v_(m+1)=v_1)。我们用σ(C)表示圈C的弦数,σ(G)表示图G中弦的最大数目。     

包装(P,P—1)(P,P)图对和Slater问题

设G是简单无向图。V(G),E(G)分别表示G的顶点集和边集。如果|E(G)|=|V(G)|-K,则称G是(P,P—K)图。对于同阶图对{G_1,G_2},如果G_1与的某个子图同构,则称图对{G_1,G_2}是可包装     

关于禁用子图与Hamilton性的新结果

不含导出子图同构于K_(1,3)或F的图称{K_(1,3),F}-free图.设图G含有无弦的点控制圈(简称VD-圈):C=C_1C_2…C_kC_1,并假定依下标顺序给定一正向.用C_(ij)表示沿C的正向从C_i到C_j的一段道路.如果{C_i,C_j}是G的2-割集,当G无爪(K_(1,3)-free)时,G-{C_i,C_j}恰有两个分支.用G_(ij)表示G的满足G_(ij)∩C=C_(ij)的极大连通子图.设P=v_0v_1…v_(d-1)v_d是G的一条直径路,X={x∈V|d(x,P)>l}.当G是{K_(1,3),F}-free图且d≥3时,同文献[1]定义     

四维球面上Grassmann丛的一些性质

1.设S~4表示四维球面,G_2(TS~4)为S~4上的具有通常的黎曼度量与殆复结构的Grassmann丛.设k是G_2(TS~4)的K(?)hler形式.若dk的(1.2)对部分恒为零,则称G_2(TS~4)为(1.2)辛流形.在本文中,我们将证明下面的结果:定理 设h_ 和J~G_±分别是G_2(TS~4)上的Riemann度量和殆复结构(t>0).则(G_2(TS~4)·J_~G_±·h_ )对于任何正数t不可能是(1.2)辛流形.特别,它不能成为K(?)hler流形.     

由一类图的着色导出的素数子集的分类

设P表示全体素数的集合,D(?)P。令G(Z,D)表示这样一个图:它的顶点集是全体整数的集合,两个顶点x和y之间有边连结当且仅当|x—y}∈D。Eggleton,Erds和Skilton等在文献中证明了:不论对任何素数子集D(?)P,图G(Z,D)的色数至     

关于交错群的特征性质

用“阶”来刻划群是一个很有意义的工作。我们已用群阶和元的阶之集给出了交错群A_n的特征性质。这里再用有限单群分类定理给出A_n的两个新刻划: 定理1 设G为有限群,如果对于任意质数p都有,其中那么G(?)A_n。 定理2 设G为有限群,r_n为不大于     

有限单群的一种新刻划

在本世纪70,80年代,Kwok Marcel等和Adilson等人证明了PSL(2,2~m),G_2(q),J_1可由其特征标表唯一决定.本文将证明如下:主要定理 设G是有限群,M是单群,G和M有相同的特征标表,则G(?)M.我们的证明思路是这样:由文献[5]知,要证明主要定理只需证明B_n(q)和C_n(q),q为奇质数幂,不能有相同的特征标表.我们下面去证B_n(q)和C_n(q)的共轭类长度之集合不同.     

2连通无爪图的最长圈

本文所涉及的图都是有限无向简单图。设G是一个图,总用V(G)、E(G)、c(G)分别表示G的顶点集、边集、周长,而令p=|V(G)|。设U(?)(G),总用G[U]表示G中由U导出的子图。如果对于任意U(?)V(G),总有G[U](?)K_(1,3),则称G为无爪图。设λ=min{d(u)+d(v)|u,v∈V(G),uv(?)E(G)},δ=min{d(u)|u∈V(G)},其     

具有最多边的唯一因子图

§1.引言 设G=(V,E)是简单图,V和E分别是G的顶点集和边集。n=|V|称为顶点数,m=|E|称为边数。设S(?)V,从G中去掉S得到的子图,用G-S表示,就是V-S生成的子图。 G的两条边e_1,e_2若有一个公共端点,称为是关联的.设F(?)E是G的边子集,F中任     

块中圈含弦的最大数目及其极图刻划

设C为简单图G的圈,我们称导出子图G[C]的不在C上的边为C的弦。本文证得:设G是2-连通图且|V(G)|≥2n+1,n≥3。若G的最小度δ(G)≥n,则G含一个圈,其弦数至少为n(n-2)+1,除非G是K_(n,m)(m>n)或Petersen图。从而Gupta,     

1坚韧图最长圈的新的充分条件

本文所涉及的图都是有限无向简单图。设G是一个图,用V(G),B和c(G)分别表示G的顶点集、边集和周长,d(u,v)表示u和v间的距离,且设p=|V(G)|。     

一个Ringel猜想的证明

本文仅讨论简单无向图.图G被称为是一个极大平面二部图(以下简称为mpb图),如果:1)G是二部图.2)G是平面图.3)若u,v∈V(G),(u,v)∈E(G),则G+(u.v)或者不满足1)或者不满足2).为简便,不防将本文所提到的平面图本身视为它的一个平面嵌入.设H是G的一个边导出子图.H在G中的边补图,记为(?),定义为E(G)\E(H)在G中的边导出子图.特别地,如果T是G的一棵树,称(?)为T在G中的上树.     

图的度和、连通度和控制圈

令Ｇ是一个ｎ阶图.设Ｃ是Ｇ中的一个圈,如果Ｇ-Ｖ(Ｃ)是空图,那么称Ｃ是控制圈.令δ,κ和α分别表示图Ｇ的最小度、连通度和独立数.用σｋ表示Ｇ中任意ｋ个独立点的度和的最小值.Ｂａｕｅｒ等人[1]证明了:设Ｇ是ｎ阶2连通图.若σ3≥ｎ κ,则Ｇ是Ｈａｍｉｌｔｏｎ图.本文证明了:定理　设Ｇ是ｎ阶3连通图.若σ4≥ｎ 2κ,则Ｇ包含一个最长圈Ｃ,使得Ｃ是一个控制圈.界ｎ 2κ是最好可能的.我们能构造一类图,它们满足定理假设,但不是Ｈａｍｉｌｔｏｎ的.根据定理,我们有如下结论:推论1　设Ｇ是ｎ阶3连通图.若σ4≥ｎ 2κ并且δ≥α,则Ｇ是Ｈａｍｉ…     

自由C*-代数与非交换Hahn-Banach定理中的完全收缩扩张的唯一性问题

1 引言及主要结果Arveson 把经典的Hahn—Banach扩张定理推广到了C-代数的自伴线性闭子空间上.从此,许多数学工作者对Arveson扩张定理作了推广,下述结果属于G,Wittstock,命题1.1(见文献[2]定理4.2)设X是-算子空间,A是一有单位元的 C-代数且A(?)X,若(?):X→B(H)是一完全收缩映射,则存在完全收缩映射(?):A→(H)使得(?)|X=(?)且||(?)||_cb=||(?)||_cb利用该命题易得:推论1.1 设X与Y均为算子空间且Y(?)X,若(?):Y→(H)是一完全收缩映射,则存在完全收缩映射(?):x→B(H)使得(?)|Y=(?)且||(?)||_cb=||(?)||_cb但命题1.1中的(?)的唯一性问题从未被人涉及,本文用自由C-代数和遗传C-代数为工具,给出了命题1.1中扩张(?)对任何Hilbert空间H均具唯一性的一个充要条件,即下述的:定理1.1 设X和Y均为算子空间,且Y(?)X,1∈X,则下述等价:(1)对每个Hilbert空间H及每个完全收缩映射(?):Y→B(H),都唯一存在完全收缩扩张映射(?):x→B(H)使得(?)|Y=(?)且||(?)||_cb=||(?)||_cb(2)C(Y)是C(X)的遗传C-子代数,定理1.2 记号同于命题1.1,则对每个Hilbert空间H,(?)均唯一存在的充要条件为:I(X)是A的遗传C-子代数,其中I(X)是由X生成的A的C-子代数,     

补图的连通度

我们构造了一组图,以证明下列的定理。定理1 若p和d为满足p-2>d>1的整数,pd为偶数,则存在一个有P个点的图G,它是d度正则的,且