若干图参数的关系

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

全着色边临界图的全色数

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

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

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

图与补图的n-全色数

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

关于全图的强完美性

定义1 简单图G的最大完全子图的阶数,称为G的团数,简记作ω(G)。定义2 若对简单图G(V,E)的任意导出子图G[S](S(?)V(G)),均有     

实半单Lie群的正交实表示

严志达与张大干在文献[1]中,给出了实半单Lie群的有限维实表示的分类。本文将利用Vogan在文献[2]中提出的最低K型的概念,讨论实半单Lie群的正交表示设G为实半单连通Lie群,K为G的极大紧子群,分别为它们的Lie代数。V是一个实Hilbert空间。π:G→End(V)为一个同态。且π(g)v(g∈G,v∈V)为G×V到矿V的连续映射,则称(V,π)为G的一个实Hilbert表示。若π(g)同时又是正交算子(保持内积不变),则(V,π)称为G的正交(实)表示。若V中没有π(G)的非平凡不变闭子空间,则称(V,π)不可约。以下恒假定(V,π)为G的不可约正交表示。记(V~c,π)为(V,π)的复化。     

关于外平面图的全色数

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

关于全着色猜想

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

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

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

图的支配数与全独立数、全覆盖数的关系

确定图的独立数、覆盖数、支配数等不变量的问题,已公认为困难问题,因而研究这些不变量之间的关系是有意义的。定义1 对图G(V,E),设σ(?)V,若V中     

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残留图,如果对     

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

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

关于连通图幂中边不交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为偶数     

图和补图线荫度的关系

定义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的最小整数.…,,)简记作图和补图线荫度的关系@张忠辅$兰州铁道学院 @王建方$中国科学院应用数学研究所!北京 @徐登洲$西北师范大学~~     

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

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)]     

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

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

关于图论中的三个B.Zelinka猜想

本文中未给定义的名词术语和未加说明的符号记法都可以在文献[1]中找到。 一、关于方体图可达划分数猜想 设G是无向图,如G的点集V(G)的子集D满足对任意的v∈V(G)-D,存在u∈D,使得u与v邻接,则称D是G的一个可达集。最小可达集的基数称为可达数,记作r(G),V(G)可以划分成若干不交可达集的并,划分的最大基数称为G的可达划分数,记作d(G)。确定n方体Q_n的可达数和可达划分数是一个还没有解决的问题。Zelinka得到了一个部分结     

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

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

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