混合Ramsey数x_2(m,K_(1,n))的下界

一个图G的全色数x_2(G)是指着色G的边和顶点使相邻、关联元素均着不同颜色所需要的最少颜色数。对于正整数m和星形图K_(1,n),混合Ramsey数x_2(m,K_(1,n))是这样的最小正整数p,使得任一p阶图H或者     

关于全着色猜想

着染简单图G=(V·E)的元素,使V∪E的任何两个相邻或相关联的元素均有不同颜色,所需要使用的颜色的最少数目被称为G的全色数,记为x_T(G)。1965年M.Behzad提出了著名的全着色猜想:     

高度图的全色数

定义1 图G(V,E)的染色x:V∪E→{1,2,…}满足 (ⅰ)邻点和邻边染色不同; (ⅱ)点与其关联的边染色不同,则称π为G的全染色。 定义2 G的全染色π所用的最少颜色数,称为G的全色数,简记为x_2(G)。     

关于外平面的完备色数

对平面图G(V,E,F),设f_1、f_2∈F,则当且仅当f_1与f_2共边时,称f_1、f_2相邻。定义对平面图G(V,E,F),使V∪E∪F中相邻、相关联元素均染为不同颜色所用的最少颜色数,称为G的完备色数,记为X_c(G)。引理令⊿(G)表示G的最大度,则对     

1坚韧图的Hamilton性

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

关于边不交的Hamiltoh圈

本文所讨论的图均为无向的简单图。用δ(G)表示图G的最小度。一个图G称为Ore-(k)型图,如果任一对不相邻顶点“和v都有d(u)+d(v)≥|V(G)|+k(k为整数)。     

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上的任一边均在点数不     

关于A.Ainouche和N.Christofides的一个猜想

一、引言 Ainouche和Christofides提出一个猜想:设a,b为2-连通图G=(V,E)的两个不相邻顶点,若,有,则G是Hamilton图当且仅当G+ab是Hamilton图。     

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

图与补图的n-全色数

定义1 对图G(V,E)和自然数n,对其长度不大于n的路上所有点(或所有边、或所有点和所有边)均染为不同色,其所用颜色的最少数目称为G的n-色数(或n-边色数、或n-全色数),简记作X_n(G)(或X′_n(G)、或X_n~T(G))。     

图与其补图覆盖数间的关系

对图G(V,E),,使得V∪E中的任一元素或在A_T中,或与A_T中的元素相邻,或与A_T中的元素相关联,则称A_T为G的全覆盖;G中元素数最少的全覆盖,称为G的最小全覆盖;G的最小全覆盖中的元素数,称为G的全覆盖数,并简记作α_T(G) 设α(G)、α′(G)分别表示图G的(点)覆盖数、边覆盖数,G~c表示G的补图,则     

若干图参数的关系

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

关于路图P_3(G)的Hamilton性的两个结果

“路图”是线图概念的发展.给定一个图G及自然数k≥2,路图P_k(G)的顶点是G中k个顶点的路P_k;两条路P_k在路图中是相邻的,如果它们的并是P_(k+1)或C_k.为     

关于J.A.Bondy的闭包重构猜想

一、引言一个图G是指一有序对(V(G),E(G)),其中V(G)是G的点集,E(G)是G的边集。这里我们仅限于讨论有限、无向、不含环及重边的图。C_k表示长为k的圈,d_G(x)表示G中点x的度。     

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

设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,E),由V中互不相邻的点组成的一个集合,称为G的一个独立集;而β(G)=max{|B||B为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是一个连通图且t为实数,若对V(G)的每个子集S,tω(G—S)≤|S|,其中ω(G—S)是G—S的分支数,则称G是t坚韧图。显然,1坚韧图是2连通的,图G的周长c(G)是指G的一个最长圈的长度。虽然对2连通图的周长的研究已有若干结果,但对1坚韧图周长的研究尚少。本文只讨论有限、无向、无环及无重边的图,且块均指非平凡块,所用术语及记号同文献[4],主要结果是如下定理。     

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

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

Hamilton图泛圈性的Ore类条件

在本文中,所有的图都是简单图,未定义的术语是常见的。众所周知,一个n阶图G,若对任何点对x,y;xy(?)E(G)总有d(x)+d(y)≥n,则G是Hamilton图(Ore,1960);进一步,G是泛圈图或二部图~K(n/2),n/2(Bondy,1971年)。