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

每个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有平凡     

大次和的1-坚韧图中的最长圈

给定一个图G,以‘(G)表示G的周长,并记一(。卜Mi·{客“(一):‘一,ng一Li的结果:设G是”阶2一连通图,若厅(G))n李3.则G是哈密尔顿图. 推论2设G‘留;,若生(3,一23)2,》15奇数;1一2r|l!|||夕、||||书纷we A\是G的无关集a3(G)(3,一16),》16偶数;·3(。卜Mi·{客己(一卜!愈N(一,!”(14。:,。2,,3}是G的无关集则G是哈密尔顿图. 该推论改进了G〔罗1,若内(G)Fa夕bender的结果:设、。)一Mi·{{(知一14),(,)1一2李|训州日N(,‘:{,,,,2,。丹是G的无关集·、(‘卜Mi·{{立N(一)卜{一提使自N(。)铃价的无关集13),则G是哈密尔顿图. 推论3.设G…     

K_4单群的分类定理

称群阶的相异素因子恰为n的有限单群为K_n单群。利用单群的分类定理本文证明了: 定理1 设G为K_4单群,则G同构于下述群之一: (Ⅰ)L_2(2~4),L_2(2~r),r≥5,2~r-1是Mersenne素数,是一素数的方幂。     

关于两类图的整和数

本文中的图均指无向简单图,以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(G),E(G))是一个图,e∈E(G)是G的一条边,如果对G—e的任意满足G—e e’(?)G的加边e’,都有e’=e,则称e为G的不动边.如果对满足G—e e’(?)G的加边e’,都存在G—e自同构映射将e的两个端点分别映到e’的两个端点,则称e为同构不动边.由此定义可知,当e是不动边时,它也是同构不动边.不动边的概念来源于图的边重构猜想.Sheehan首先提出不动子图的概念,并用之研究了边重构猜想.当不动子图仅为一条边时,即为不动边.文献[3]中的强迫边(forced edge)也是不动边.反之,一个边可重构图中的不动边也必是强迫边.这样,就可以通过证明一个图的     

Halin图的边面全色数

定义1 将点数至少为4、所有非一度点(内点)度数至少为3的树T嵌入到平面内,再作一圈C_n.连接T的n个一度点(叶点)所成的平面图,称为Halin图;T称为Halin图的特征树;以C_n为边界的面称为Halin图的外面,其他面称为内面;面边界上的点数为奇数时,称该面为奇面,否则为偶面.平面图两面相邻,当且仅当两面至少有一条公共边.定理1 若G是Halin图,则(i)当G的最大度△(G)≥6时,有X_(ef)(G)=△(G);(ii)当△(G)=3时,有4≤X_(ef)(G)≤5,而X_(ef)(G)=5当且仅当外面f_0的边界上存在一条路P,使得P上的任一边均在点数不     

2连通正则无爪图中的Hamilton圈

本文讨论的图都是无向的简单图。图G称为无爪的,如果G没有同构于K_(1,3)的顶点导出子图。 关于2连通正则图的Hamilton性,1980年B.Jackson证明了:若G是2连通、k正则图,且G的顶点数不大于3k,则G是     

关于UC图

J.A.Bondy和U.S.R.Murty收集了若干尚未解决的问题,其中有R.C.Entringer于1973年提出的问题10:确定简单图G,使得对应于3≤l≤v的每一个l,G恰有一个长为l的圈(这里v表示图G的顶点数)。     

Hamilton图的一个充分条件

设G=G(V,E)为简单图。d(u)表G中顶点u的度,d(u,v)表顶点u与v的距离。ω(G)表G的分支个数。本文证明了下述定理。 定理 阶数n≥3的简单图G满足下述两条件:     

K_(1,3)-free图中的圈

本文说的是简单图。 设G是任一个n阶的图。如果G中有长为n的圈,则G是哈密顿图。如果对每个k,3≤k≤n,G含有长为k的圈,则说G是泛圈图。如果对G的每个顶点v,图G中都有长为k的圈经过顶点v,则说G是点k圈图。如果对每个k,3≤k≤n,G都是点k圈图,则说G是点泛圈图。     

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

设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,     

N阶完全图K_N的t边着色

如果N阶完全图K_N的边用t种颜色着色,则K_N称为是t边着色的。图F_i,l≤i≤t的Ramsey数n(F_1,…,F_i)是这样的最小正整数,使得对于任意一个i边着色完全图K_n,都可以在其中找到某个子图F_i,它是用第i种颜色着色的。当F_1=     

图的生成环及线图的Hamilton性

所讨论的图都是无向的、有限的简单图。图G的一个生成环(S-circuit)指的是一条通过图G所有顶点的闭迹。一个连通图称为几乎无桥图,如果G的任一桥至少关联一个度为1的顶点。1977年,F.T.Boesch、C.Suffel和R.Tindell提出了有生成环图的     

全着色边临界图的全色数

定义 对于简单图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。     

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

边色数的分类问题及其有关性质

设图G为简单连通图,由Vizing定理可知△(G)≤x′(G)≤△(G)+1。其中,△(G)表示图G的最大顶点次,x′(G)是图G的边色数。若x′(x)=△(G),则称G为第一类图,并记为G∈C~1;若 x′(G)=△(G)+1,则称G为第二类图,记为G∈C~2。本文的目的在于讨论边色数的分类问题及其有关性     

图到其迭线图的子图的同构

如果存在一个图G到图H的子图G′上的同构φ,我们就记作GH,说G嵌入到H内,而φ称为G到H内的一个嵌入。1982年,D.Bauer和R.Tindell对既不是道路,也不是K_(1,3)的图G定义了一个不变量∧(G),它是使GL~n(G)成立的最小的n,n≥1。他们研究了∧(G)=1的图,并提出研究∧(G)=2的图,以及对所有树T,确定∧(T)这两     

图的连通度与Hamilton连通性

一、引言 我们讨论的图均为简单图,K和α分别表示图的连通度和独立数。我们采用文献[1]的术语和符号,并记G_n~k={G丨G为n阶k-连通图},H_e={G丨G是Hamilton连通图},用P_H(u,v)表示从u到v的Hamilton路。图G中的路P称为控制路,如果G[P(G)\V(P)]均为孤立点.给出图G中的一条(x,y)-路P,总认为是从x到y定向,表示的反向。若u,v∈V(P),则uv表示P上沿从u到v的路。又u≠y,v≠x,则u~+和v~-分     

关于连通图幂中边不交1-因子

我们总假设G=(V,E)为p阶连通简单图,n为自然数.G的n次幂图G~n定义如下:V(G~n)=V(G),E(G~n)={uv:d_G(u,v)≤n,u,v∈V(G)},式中d_G(u,v)是u和v在G中的距离. 1984年,Nebesk(?)证明了:当P为偶数