图的λ_6-最优性的领域交条件

文章给出了满足一定条件的图的λ6-最优性的领域交条件.设图G是连通图,若对G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥10且｜X5｜≤5,则G是λ6-最优的;若对于连通图G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥10且对图中每个三角形T至少存在一个顶点v∈V（T）使得d（v）≥v2＋5,则G是λ6-最优的.     

图的λ4-最优性的邻域交条件

文章给出了图的λ4-最优性的邻域交条件.设图G是阶至少为34的λ4-连通图,若对G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥6且ξ4（G）≤3n（G）/2＋3,则G是λ4-最优的;若对于λ4-连通图G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥6且对图中每个三角形T至少存在一个顶点v∈V（T）...     

树图的外围维纳指标的下界

设G=(V,E)为简单连通图.对v∈V(G),顶点v的离心率ε(v)=max{d(u,v)│u∈V(G)}, d(u,v)为图G中顶点u,v间的距离.图G的直径为d(G)=max{ε(v)│v∈V(G)}.外围顶点集P(G)指图G中满足ε(v)=d(G)的所有v=V(G).图G的外围维纳指标为■.首先讨论了当树图T的外围顶点个数确定时,它的第二下界;然后讨论了当树图T的顶点数目确定时,其对应的PW(T)的最小值,及达到其最小值的极图.     

变换图G++-的独立数

本文所研究的图G的变换图G＋＋-是以V（G）∪E（G）作为顶点集的图,它的两个顶点u与v被一条边连接当且仅当下列情形之一成立：（i）如果u,v∈V（G）,那么它们在G中邻接;（ii）如果u,v∈E（G）那么它们在G中邻接;（iii）如果u与v一个属于V（G）而另一个属于E（G）,那么它们在G中不关联.同时给出了变换图G＋＋-的独立数的公式。     

关于USP图

给定一个连通图C,u是G的一个顶点,T是G的一棵生成树,如果对任意的v∈V(G),d_T(u,v)=dG(u,v),则称T是G中顶点u的距离树。例如,K_(2,2)中每个顶点都有两棵距离树。 Ore已经证明了对于已给一个连通图G和它的一个顶点u,这样的距离树是存在的。Chartrand和Schuster称所有距离树都同构的连通图为具有唯一距离树的图,並且讨     

含有割点的图的测地集

对于图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）}/．     

关于二分图的F-Hamilton性

设G是一个简单图,任意e∈E（G）,定义e=uv在G中的度d（e）=d（u）＋d（v）,其中d（u）和d（v）分别为顶点u和v在G中的度数。设F是二分图G的一个1-因子,如果G中有包含F的Hamilton圈,则称G是F-Hamilton的;给出了二分图是凡Hamilton的一个新的充分条件。     

λ_4-最优二部图的领域交条件

文章给出了二部图是λ4-最优的一个领域交条件.设n为一个不小于8的正整数,令G=（X∪Y,E）为一个n阶二部图且ξ4（G）≤n/2.若G有一个饱和X或Y中所有顶点的匹配且对任意的u,v∈X和u,v∈Y都有｜N（u）∩N（v）｜≥4,则G是λ4-最优的.     

Cartesian积图的分解

若图G的边集能划分成两两不相交的若干个子集，使得每个子集都导出相同的子图H，则称G存在H分解。两个图G=（Vi,Ei）（i=1，2）的Cartesian积，记作G1□G2，其顶点集V=V1×V2，边集E={（（u1，u2），（v1，v2））｜u1=v1∈V1,u2v2∈E2或u2=v2∈V2，u1v1∈E1}。本文给出了路和圈的Cartesian积图存在只分解的充要条件。     

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成立.     

完全二部图K7，n当n较小时的点可区别IE-全染色

设G是简单图,图G的一个中k-点可区别IE-全染色（简记为k-VDIET染色）。f是指一个从V（G） E（G）到｛12,…,k）的映射,且满足：uv∈E（G）,有f（v）;u,v∈V（G）,u≠v,有C（u）≠C（v）,其中C（u）={f（u）}{f（u）}uv∈E（G）。数min{k｜G有一个k-VDIET染色｝称为...     

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

关于哈密尔顿图和哈密尔顿连通的两个基本结果是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}|.     

K5,5,p的点可区别的IE-全染色（p≥2 028）

图G的IE-全染色f是指对?u,v∈V（G）,使得f（u）≠f（v）的一个一般全染色,其中u,v相邻,V（G）是图G的顶点集.设f是图G的IE-全染色,图G的一个顶点x在f下的色集合C（x）是指由x及x的关联边的颜色所构成的集合（非多重集）.若图G的任意两个不同顶点的色集合不同,则f称为图G的点可区别的IE-全染色（简记为VDIETC）.利用色集合事先分配法、构造染色法及反证法探讨了完全三部图K_5,5,p（p≥2028）的点可区别的IE-全染色问题,确定了K_5,5,p（p≥2028）的点可区别的IE-全色数.     

无爪图的泛连通性

证明了如果G是3连通无爪图,且G的每个导出子图A、子图T都满足φ（α、α2）,则G是泛连通图（当u、v∈V（G）,d(u,v)=1时;G中可能不存在（u,v）-k路,k=2,3,4除外）。     

Hamiltion图的一个充分条件

证明如下结果：G是简单图满足条件：对G中任一对不相邻顶点u、v有max{d(u),d(v)} ｜N(u)∪N(v）｜≥n-1；且对任意T包含V（G），有ω（G\)≤｜T｜，则G是Hamilton图。     

mPn 的顶点被多重色集合可区别的一般边染色

简单图 G 的一个一般边染色是指若干种颜色关于图 G 的所有边的一个分配,不要求相邻的边被分配不同的颜色。设 f是 G 的使用了 k 种颜色的一般边染色,若对u,v∈V（G）,u≠v,都有与 u 关联的边的颜色构成的多重集合异于与 v 关联的边的颜色构成的多重集合,那么称 f是使用了 k 种颜色的顶点被多重色集合可区别的一般边染色。对 G 进行顶点被多重色集合可区别的一般边染色所需的颜色的最少数目记为 c（G）,并且称 c（G）为图 G 的顶点被多重色集合可区别的一般边色数。讨论了 m 个 Pn 的点不交的并 mPn 的顶点被多重色集合可区别的一般边色数。     

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

设G是简单图,图G的一个k-点可区别IE-全染色（简记为k-VDIET染色）f是指一个从V（G）∪E（G）到{1,2,…,k}的映射,且满足：A↓uv∈E（G）,有f（u）≠f（v）;A↓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-全色数,记为χut^ie（G）。本文给出了完全二部图K5,n（n≥6）的点可区别IE-全色数。     

变换图G++-的连通度

本文所研究的图G的变换图G++-是以V(G)∪E(G)作为顶点集的图,它的两个顶点u与v被一条边连接当且仅当下列情形之一成立:(ⅰ)如果u,v∈V(G),那么它们在G中邻接.(ⅱ)如果u,v∈E(G),那么它们在G中邻接.(ⅲ)如果u与v一个属于V(G)而另一个属于E(G),那么它们在G中不关联.文章给出了变换图G++-的连通度的一个下限.     

点可区别全色数的一个上界

设G是简单图，f是从V（G）UE（G）到{1,2，…，k）的一个映射．对每个u∈y（G），令c（u）={f（u）}v∈V（G）,uv∈ E（G）}．如果，是k-正常全染色，且对任意u，v∈V（G）（u≠v），有c（u）≠c（v），那么称f为图G的k-点可区别全染色（简记为k-VDTC）．数χvt（G）=min{k｜G-有k—VDTC}称为图G的点可区别全色数．通过应用概率方法，证明了对任意最大度A≥2的图G，χvt（G）≤32（△＋1）．     

固定直径树的距离平方和问题

定义图G中所有点对间的距离的平方和为S(G)=∑uv∈VGd2G(u,v)=1/2∑v∈VGLG(v),其中dG(u,v)为图G中任意顶点u,v之间的距离,LG(v)表示图G中点v到其它点的距离的平方和。在所有直径为d的n顶点树中分别确定使S(G)最小和第二小的树。