关于外平面的完备色数

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

p阶临界2-边连通图的最大边数

设G=(V,E)是p阶简单无向图。 若G是2边连通的,设v∈V,若G-v不是2边连通的,则称点,是G的临界点。若G的每一点都是临界点,则称G是临界2边连通图     

高度图的全色数

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

全着色边临界图的全色数

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

具有最多边的唯一因子图

§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中任     

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

对图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的补图,则     

包装(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}是可包装     

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

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

m-k_n×k_s残留图

本文将讨论m-k_u×k_s残留图。定义1 图G=(V,E)为简单图,u∈V,集合N~*(u)={v∈V|v与u邻接}U{u}叫做u的闭邻域。定义2 G叫做F残留图,F是指定的图,如果对每一点u∈V(G),G-N~*(u)≌F,(≌表示同构)递归地定义,图G叫做是m-F残留图,如果对     

氮化硅纳米粒子的量子限制效应

G是一个连通图,SV(G)和u∈V(G),我们记 N(S)={v∈V(G)\S:存在w∈S使得vw∈E(G)}, N(u)={v∈V(G):uv∈E(G)},分别称为S和u点在G中的邻域.进一步,N(u)=N(u)∪{u},u点的闭邻域,和 G(u)=G[N(u)]     

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

几类由PLD确定的连通图

给定简单图G=(V,E),其中V是顶点集,E是边集。若对V的两个顶点u,v,在G中存在含有i个顶点的一条(u,v)路,则称性质P_i(u,v)成立。令S_i(2≤i≤n)是G中有性质P_i(u,v)的无序顶点     

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

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

荫度与独立数、覆盖数的关系

定义1对图G(V,E),由V中互不相邻的点组成的一个集合,称为G的一个独立集;而β(G)=max{|B||B为G的独立集}     

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

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

冠C_(2n)☉K_1协调猜想的证明

一个图G=(V,E)称为是协调的(harmonious),如果存在一个单射h:V(G)→Z_q,其中Z_q={0,1,……,q-1},q=|E(G)|,由此导出的边标号h~*(u,v)=h(u)+h(v)(modq)是1-1的。若G是树,则允许有且仅有两点的标号相同,这时h称为G的一个协调标号。若上述映射导出     

有限交换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}。     

图与补图的n-全色数

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

关于外平面图的全色数

对于简单图G(V,E),使得VUE的任何两个相邻或关联的元素都着有不同颜色的最少颜色数,称做图G的全色数,简记作x_T(G).定理1 若G为无割点的外平面图,△(G)≥4,则G必至少有下列情况之一:(ⅰ) G有两个2度点相邻;(ⅱ) G有一个2度点与3度点相邻;(ⅲ) G有两个2度点共邻于一个4度点,