关于顶点凝聚度的几个定理

本文研究图Ｇ的顶点、是负点（Ｃ（ｖ）＝Ｋ（Ｇ）－Ｋ（Ｇ－ｖ）＜０， 零点（Ｃ（ｖ）＝０）、正点（Ｃ（ｖ）＞０）的充要条件。     

λKυ分解为一个二部图

λKυ是λ重υ点完全图，对于有限简单图G，所谓图设计G-GDλ(υ)是序偶(X，A)，其中X是Kυ的顶点集，而区组集A为AKυ的全部边的1种分拆，其中每个成员(区组)都是与G同构的子图．利用“差方法”、“带洞图设计”等工具，结合一系列小设计的构作，对1个6点8边图G1的图设计进行了讨论，并证明了：存在G1-GDλ（υ）←→λυ（υ-1）≡0（mod 16),υ≥6     

在一类限定3-正则图中:β≥ n/3

G（V，E）是一个图。如果点集I是V的子集且＜I＞是空图，则称I是独立集，如果点集X是V子集且N[X]=V，则称X是控制集。如果点集I是V的独立集且又是控制子集，则称I是独立控制集，即极大独立集，β(G)=max{|I|I是G的独立集}，称β(G)是图G的独立数。在不发生混淆的情况下，用β表示图G的独立数，可以证明：在限定3－正则图中，β≥n/3，其中n是图的阶。     

几类7点7边图的图设计与最优填充

设λKv是λ重ν点完全图，G是无孤立点的有限简单图。将G－设计（G－填充）记作（ν，G，λ）－GD（（ν，G，λ）－PD）是指一个序偶（X，B），其中X是完全图Kν的顶点集，B是Kν中间构于G的子图（区组）的集合，使得Kν中每条边恰好（至多）出现在B的λ个区组中。讨论了3类7点7边图Gi(i=1,2,3)的图设计及最优填充问题，并给出了（ν，Gi,1)-GD及（ν，Gi,1)-OPD(i=1,2,3)存在的谱。     

距离图的点荫度

实数距离图G(R，D)是顶点集为实数轴上的所有点，顶点u,v∈R相邻当且仅当|u-v|∈D，其中D是一个正实数集．讨论了当D为1到δ的区间时，实数距离图G(R，D)的点荫度．特别地，当3D是某正整数集合，Z是整数集时，得出了整数距离图G(Z，D)的点荫度的几个上界．     

含有割点的图的测地集

对于图G内的任意两点u和v,u-v测地线是指在u和v之间的最短路．I（u，v）表示位于一条u-v测地线上所有点的集合，对于S包含V（G），I（S）表示所有，（u，v）的并。这里u，u∈S．G的测地数g（G）是使I（S）=V（G）的最小点集S的基数．图的每个最小测地集都不包括它的割点，如果图G是一个有n≥3个顶点，k≥1个割点的块图．那么g（G）=n-k．树T有n≥2个顶点，l片叶子。如果将树T的所有点ui用图Hi来代替。用Hi∨Hj来代替树T的所有边uivj∈E（T），将得到的新图定义为Tn（H）。有g（Ta（Kd））=ld和g（Tm（Cd））≤min{[d/2]l。2（n-l）}/．     

图的T-边匝

假定G是一个图，且T是一个包含零的非负整数集，图G的一个T-染色是指分配到图G的每个顶点x上的非负整数f(x)，使得当任意x，y∈E(G)时，|f(x)-f(y)|不属于T．T-染色f的edge Span是对G的所有边xy中|f(x)-f(y)|的最大值，图G的T-edge span是指G的T染色的edge Span的最小值．该文主要研究了对T={0，1，2，…，κ-1}Cn^d图的T-edge Span，其主要结果是完全解决了该图的T-edge span的计算问题．     

直径图为11圈的7距离集研究

如果平面点集X中的任意两点确定的互异距离数为k,则称X为k距离集。用d(x,y)表示平面上互异两点x,y之间的距离,记X中的最大距离为直径D=D(X)。直径图DG(XD)是由X中所有直径构成的图,XD表示其顶点集。讨论了当X是一个7距离集时,直径图DG(XD)的构型。利用DG(XD)中最多包含一个圈,且只能为奇圈的特性,以及直径所具有的特殊性,证得当直径图为11圈时,其顶点集XD恰好为某正十一边形的顶点集。     

关于图的哈密尔顿性的一些新的结果

关于哈密尔顿图和哈密尔顿连通的两个基本结果是Ore给出的:设G是一个n(n≥3)阶图,如果对于G的任意一对不相邻顶点u,v,有d(u) d(v)≥n或n 1,则G是哈密尔顿图或哈密尔顿连通的.设G是一个图,对于任意u∈V(G),令N(u)表示u的邻点集;对于任意U∈V(G),令N(U)=∪u∈UN(u).本文利用插点方法,给出了关于k或(k 1)-连通图(k≥2)G是哈密尔顿的,哈密尔顿连通的或1-哈密尔顿的统一证明.其充分条件是关于|N(S)| |N(T)|与n(S ∪T)的不等式,这里S,T是图G的任意两个不交的独立集,并且|S|=s,|T|=1,S∪T也是一个独立集,这里n(S∪T)=|{v∈V(G):dist(v,S∪T)≤2}|.     

关于六点八边图的图设计

设Kv是一个v点的完全图，G为一个不含孤立点的简单图。Kv的一个G-设计，常记为（v,Gi,)-GD，是指一个二元组（X，B），其中X为Kv的顶点集，B是Kv的一些子图（亦称为区组）构成的集合，使得每一个区组与G同构，且Kv的任何一条边恰在B的一个区组中出现。本文讨论了三类六点八边图（v,Gi,1)-GD（i=1,2,3)的图设计存在问题，即（v,Gi,1)-GD(i=1,2,3)存在的充要条件是v≡0,1 mod(16）且v≥16。     

极大3等周边连通图的充分条件

k等周边连通度是一个比边连通度更可靠的网络可靠性参数。 连通图G的k等周边连通度定义为γk(G)=min{［X,X-］:XV(G),X≥k,X-≥k},其中X-=V(G)＼X。令βk(G)=min{［X,X-］:XV(G),X=k}。图G是极大k等周边连通的如果γk(G)=βk(G)。令G是一个阶至少为6的连通图。本文证明了如果对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足N(u)∩N(v)≥2;当u和v中至少有一个在三角形中时满足N(u)∩N(v)≥5,那么G是极大3等周边连通的。     

图的顶点子集的凝聚度──关于负集的若干定理

本文在图的顶点凝聚度的基础上［１］，把图的顶点的凝聚度的概念推广到子集Ｘ　Ｖ（Ｇ），并 研究负集的若干性质。     

完全二部图K5,n的点可区别IE全染色

设G是简单图, 图G的一个k 点可区别IE 全染色(简记为k VDIET染色) f是指一个从V(G)∪E(G)到｛1,2,…,k｝的映射, 且满足:uv∈E(G),有f(u)≠f(v);u,v∈V(G), u≠v, 有C(u)≠C(v), 其中C(u)=｛f(u)｝∪｛f(uv)|uv∈E(G)｝。 数min｛k|G有一个k VDIET染色｝称为图G的点可区别IE 全色数,记为χievt(G)。本文给出了完全二部图K5,n(n≥6)的点可区别IE 全色数。     

图是极大3限制边联通的充分条件

设S是连通图G中的一个边子集。若G S不连通且它的每个连通分支的阶至少为k,则称S是G的一个k限制边割。图G的最小k限制边割的边数称为G的k限制边连通度,记为λκ(G)。定义ξκ(G)=min{|［X,X］|:|X|=k,G［X］连通},其中X=V(G)＼X。若λk (G)=ξk(G),则称G是极大k限制边连通的。设G是一个围长至少为5的λ3 连通图。本文证明了若G中不存在5个点u1,u2,v1,v2,v3使得d(ui,vj)≥3(i=1,2;j=1,2,3),则G是极大3限制边连通的。     

K1×mCn的k-边优美指标集

设G=(V,E)是一个p点q边图.对于非负整数k,若存在双射f:E→{k,k+1,…,k+q-1},使得其导出映射f+:V→Zp,f+(u)≡∑(u,v)∈Ef(u,v)modp也是一个双射,则称此图G是k-边优美的.称EGI(G)={k:G是k-边优美的}是G的边优美指标集.在此彻底解决了图K1×mCn(mn≡0mod 2)的边优美指标集.     

Halin图的集染色

对于非平凡连通图G,G的k集染色是指映射c：V（G）→Nk,对任意顶点v∈V（G）,定义邻色集cN（v）={c（u）｜u∈N（v）},若对uv∈E（G）有cN（u）≠cN（v）,则称c为G的一个k集染色.满足上述条件的最小k值称为G的集色数,记为χs（G）.为了更快更有效地给Halin图着色,采用集染色的着色方法,证明了当p≥4时,Halin图G（Cp,Tq）的集色数是3,并且还证明了对任意的Halin图G（Cp,Tq）,有p＋1≤q≤2p-2成立.     

长圈的邻域并条件的推广

本文证明了若G为一个k(k≥2)连通简单图,最小度为,δV(G)=n≥3,X 1,X 2,……,X k是顶点集合V的子集,X=X1∪X2∪…∪Xk,且对于Xi(i=1,2……k)中任意两个不相邻点u,v,都有N(u)∪N(v)≥n-δ,则X在G中可圈。并给出几个相关推论.     

拓扑动力系统中渐近周期点的存在性

设(X,f)是一个拓扑动力系统,S是X的子集.本文首先讨论了若S为f的混沌集,则f在S内至多只有1个渐近周期点;若S为f的混沌集并且f(S)是S的子集及f所有周期点的周期都大于1,则f在S内不存在渐近周期点.然后研究了f在一般集合S内是否存在渐近周期点的条件.得到了如果当S的闭包和f的周期点集不相交且f(S)是S的子集,则f在S内不存在渐近周期点;如果存在S的f正半轨道中的某一项和f的周期点集相交,则f在S内存在渐近周期点.