一个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中的上树.     

关于两类图的整和数

本文中的图均指无向简单图,以N,Z分别表示全体自然数及全体整数集合.对子集S(?)Z(N),S上的整和(和)图定义为图G=(S,E),满足条件对u,v∈S,uv∈E当且仅当u v∈s.此时,S称为G的一个整和(和)标号.一个图称为整和(和)图,如果它同构于某一子集S(?)Z(N)上的整和(和)图.容易验证,对一个有m条边的n阶图G,G∪mK_1是一个和图,只需标定G的顶点为2~i,1≤i≤n,同时对v_i,v_j∈E(G),标定对应的孤立点2~i 2~j即可.因此,对每一个图G,存在一个最小的非负整数r,使G∪rK_1为和图,记σ(G)=r,并称为G的和数.图的整和数ξ(G)类似定义,只是标号范围放宽到整数集上.容易看到ξ(G)≤σ(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中任     

局部化扩张的Casacuberta问题

设(?)为范畴,称(?)中的态f:A→B与对象X是正交的,若f~*:(?)(BX)→(?)(A,X)为双射.对(?)中的态簇S,记S~⊥={X∈(?)|X与S中的每个态正交}.同理,对(?)中的对象簇D可定义D~⊥.偶对(S,D)称为正交偶,如果S~⊥=D,D~⊥=S.称函子E:(?)→(?)为局部化函子,如果存在自然变换η:I→E(I为恒等函子),使得对任意X∈(?),η_(EX)=E_(ηx)且η_(EX)为等价.此时也称(E,η)为幂等对.令S_E={f∈(?)|Ef为等价},D_E={X∈(?)|η_x:X→EX为等价}.由文献[1],(S_E,D_E)为(?)上的正交偶.设(?)’为(?)的满子范畴,(E’,η’)为(?)’上的幂等对,称局部化函子E:(?)→(?)为E’在(?)上的扩张,如果S_(E’)(?)S_E,D_(E’)(?)D_E.设E_1,E_2均为E’在(?)上的扩张,如果D_(E1)(?)D_(E2),则记E_1≤E_2如果函子E满足(S_E,D_E)=(D_E~⊥,D_E~(⊥⊥))(这里运算“⊥”是关于范畴(?)的),显然E为E’的扩张,称为E’在(?)上的最小扩张.如果(S_E,D_E)=(S_E~(⊥⊥),S_E~⊥),这时E也是E’的扩张,称为E’在(?)上的最大扩张.由文献[1],命题2.2,对E’在(?)上的任一扩张E,有最小扩张≤E≤最大扩张.下设(?),(?),(?)_0分别表示点标单连通CW复形,点标幂零连通CW复形与点标连通CW复形的同伦范畴,P为某一素数集,则(?),(?),(?)_0上分别存在P-局部化函子,分别记之为L_p     

(a,b,k)-临界图

本文所考虑的图皆指有限无向简单图。设G是一个图,具有顶点集合V(G)和边集合E(G)。文中未加说明的记号和定义参见文献[1]。设S(?)V(G),用G[S]表示G中由S导出的子图。用d_G(x)表示顶点x在G中的次数。设a和b是两个非负整数且a≤b。图G的一个[a,b]-因子是G的一个支撑子图H,使对任意的x∈V(H)有设。如果去掉图G的任意k个顶点所剩的图仍有[a,b]-因子,则称图G是(a,b,c)-临界图,或者说G是(a,b,k)-临界的。如果a=b=n,则简称(a,b,k)-临界图为(n,k)-临界图。如果n=1,则简称(n,k)-临界图为k-临界图。Plummer和Lovasz讨论了2-临界图的特征和性质。于青林给出了k-临界图的特征。刘桂真和于青林研究了(n,k)-临界图的特征。本文考虑a相似文献   

全着色边临界图的全色数

定义 对于简单图G(V,F),(?)e∈E(G),当 χ_T(G)>△(G)+1, χ_T(G-e)=△(G-e)+1时,则称G为全着色边临界图.其中厶(G)表示G的最大度,χ_T(G)表示G的全色数。 引理1 对图G(V,E)。(?)e∈E(G),若△(G)≥2,则 χ_T(G-e)≤χ_T(G)≤χ_T(G-e)+1。 定理1 若图G(V,E)是全着色边临界图,则 χ_T(G)=△(G)+2。     

关于完全3-分图同构因子分解

一个图G=(V,E)的同构因子分解是边集合E的一个分划:{E_1,E_2,…,E_t}使得支撑子图(V,E_1),(V,E_2),…(V,E_t)都彼此同构。如果存在把图G分成t个子图的同构因子分解,就说t能整除G,记为t|G。显然t|G的必要条件是t||E(G)|。t||E(G)|被称为关于G和t的可分条件。Harary等人证明了,当t=2,和4时,可分条件对t|K(m,     

每个4-正则简单图包含一个3-正则子图

1973年,C.Berge猜想:每个4-正则简单图包含一个3-正则子图,1979年,v.Chvátal,H.Fleischner,J.Shechan和C.Thomassen猜想:设G是奇阶4-正则图。若λ_c(G)∈{6,8},则G存在一点x,使得G—x有3-正则生成子图。(λ_c(G)是图G的边圈连通度)。本文以更一般的形式证明这两个猜想为真。 一个图G是强4-边连通的,若G是4边连通的,且对任一个基数为4的边割集5,G—S有平凡     

有限交换2-DCI群和一类3-DCI群

设G是有限群。称G的非空子集H是Cayley子集,如果G的单位元e(?)H.对于G的每个Cayley子集H定义Cayley有向图x=x(G,H),这里V(x)=G,E(x)={(a,6)|a,b∈G,ba~(-1)∈H}。     

连通、局部连通、无爪图是点泛圈图

本文只讨论有限、无向、无环和多重边的简单图。V(G)、E(G)分别表示图G的顶点集和边集。如果S(?)V(G),用G[S]表示子集S在G中的导出子图。若u∈V(G),N(u)表示u点的邻域,即邻接于u点的全体顶点的集合。     

悬图重构的两个新结果

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

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)},其     

关于禁用子图与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]定义     

关于全图的强完美性

定义1 简单图G的最大完全子图的阶数,称为G的团数,简记作ω(G)。定义2 若对简单图G(V,E)的任意导出子图G[S](S(?)V(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}是可包装     

完全等部多分图的同构因子分解——关于F.Harary,R.W.Robinson和N.C.Wormald猜想

图G(V,E)的一个同构因子分解是指边集E的一个分划{E_1,E_2,…,E_t)使得图G能够分解为t个同构因子的一个必要条件是,我们称是关于G和t的可分条件,一般说来可分条件不是充分条件。美国数     

关于Erds的加边图带宽问题

G+e表示由图G加上边e而得到的图。表示G的补图,B(G)表示图G的带宽。Erds于1971年提出下述问题: 对任意一个图G和任一条边e,是否有     

若干图参数的关系

定义1 对图G(V,E),设,若V中的点或在σ中,或与σ中的点相邻,则称σ为G的点控制集。记 σ(G)=min{|σ||σ为G的控制集}并称σ(G)为G的控制数。 类似地可定义G的边控制数σ(G)。 定义2 对图G(G,E),设E,若V∪E中的元素或在A中,或与A中的元素相邻或相关联,则称A为G的全覆盖     

形如Np的子群系可补的局部群系

本文中所有群为有限群。定义和符号参见文献[1～3]。这里给出本文常用的一些概念与符号。一个群类称为群系,如果它关于同态像和次直积是封闭的。非空群系(?)称为局部的,如果由可推得一个群类(?)称为Fitting类,如果满足以下两个条件:1)若N为G的次正规子群,则若N_1,…,N_t为G的次正规子群且N_i∈(?),i=1,…,t,则。一个群系的局部子群系如果同时是一个Fitting类,则称之为局部Fitting子群系。设(?)为某一群的集合。我们用form(?)表示由群集合(?)生成的群系,用lform(?)表示由(?)生成的局部群系,π(G)表示群G的阶的素因数的集合,表示所有幂零群的群系,N_π表示所有幂零π-群的群系,(1)表示单位元群系。群系(?)的子群系(?)_1称为在(?)中可补的,如果(?)_1在(?)的子群系格里可补,即存在(?)的子群系(?)_2,使得且.     

格蕴涵代数的滤子与结构

为了从语义角度研究命题的真值取于格上的逻辑系统,文献[1]将格与蕴涵代数相结合提出了格蕴涵代数的概念,文献[1,3～5]研究了格蕴涵代数的一些性质.本文讨论格蕴涵代数中的滤子,特别是生成滤子,并由此探讨一类格蕴涵代数的结构特征.1 滤子及其性质关于格蕴涵代数及其中滤子的定义参看文献[1].定义1 设(L,V,∧,’,→)为一个格蕴涵代数,称包含A(?)L的最小滤子(A]为由A生成的滤子.