关于圈与完全图的笛卡儿积的测地数

对于图G内的任意两点u和v,在u和v之间的最短路称为u-v测地线.I(u,v)表示位于u-v测地线上所有点的集合,对于S V(G),I(S)表示所有I(u,v)的并,这里u,v∈S.如果I(S)=V(G),那么称S是G的测地集;并把测地集的最小基数称为G的测地数,记为g(G).文章主要研究Cn×K3的测地数.     

扇图的笛卡儿积的测地数(英文)

对于图G内的任意两点u和v,u-v测地线是指u和v之间的最短路.I(u,v)表示位于u-v测地线上所有点的集合,对于V(G)S,I(S)表示所有I(u,v)的并,这里u,v∈S.G的测地数g(G)是使I(S)=V(G)的点集S的最小基数.文章研究了Pm×Fn和Cm×Fn的测地数,这里Pm表示m阶路,Cm表示m阶圈,Fn表示n阶扇图。     

关于图运算的测地数

对于图G(或有向图D)内的任意两点u和v,u-v测地线是指在u和v之间(或从u到v)的最短路.I(u;v)表示位于u-v测地线上所有点的集合,对于SV(G)(或V(D)),I(S)表示所有I(u,v)的并,这里u,v∈S.G(或D)的测地数g(G)(或g(D))是使I(S)=V(G)(或I(S)=V(D))的点集S的最小基数.G的下测地数g-(G)=min狖g(D):D是G的定向图狚,G的上测地数g+(G)=max狖g(D):D是G的定向图狚.对于两个图G和H,u∈V(G)和v∈V(H),在u和v之间加一条边,然后再收缩这条边uv所得的图,记为GuHv.本文主要研究图GuHv的测地数和上(下)测地数.     

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

定义图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)最小和第二小的树。     

图的强彩虹连通数

如果图G的任意两个顶点由一条路P连接,其中路P的每一条边着不同的颜色,则称图G为彩虹连通图.对图G的任意两个顶点u和v,G的彩虹u-v测地线是一条长为d(u,v)的彩虹路,其中d(u,v)表示最短的u-v路的长度.图G称为强彩虹连通的如果对G的任意两点u和v间都存在一条彩虹u-v测地线.图G的强彩虹连通数是指使得图G是强彩虹连通而用的最少颜色的数目,用src(G)表示.该文首先给出了一个含边不交的k-圈图的一个强彩虹连通数的上界.接着给出了这个上界取等的充分条件.     

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

设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是简单图，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）．     

图的λ_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-最优的.     

Mycielski’s图的Co-PI指标

令G是一个图,u是图G的一个顶点, TG（ u）是图G当中除了u以外的其余顶点到点u的距离之和, T（ u）＝TG（ u）＝∑u∈V dG（u,v）,Co-PI指标定义为：Co -PIv（G）＝∑uv∈E（G） T（ u）-T（ v）。文章给出了一些Mycielski’ s图的Co-PI指标的计算公式。     

关于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称所有距离树都同构的连通图为具有唯一距离树的图,並且讨     

几类和扇有关图的优美性

证明下面的结论:对任意自然数n≥2,图(K_1∨(P_n∪P_(n+1)))是(n-1)-强优美图.对任意自然数n≥3,图(K_1∨P_n~((1))∪P_n~((2))))∪G是优美图;对任意自然数n≥4,图(K _1∨(P_n~((1))∪P_n~((2))∪P_n~((3)))∪H是优美图,其中k=[n/2].P_n是n个顶点的路,G_i为含有i条边的优美图.给定优美图G_(n-1)和其优美标号f,G_(k-1)和其优美标号g,设u∈G_(n-1),v∈G_(k-1)且f(u)=g(v)=0,取不同的两边xy和x′y′,点x与u合并后得到的图记为G,点x′与v合并后得到的图记为H.     

图的点可区别无圈边色数的一个上界(英文)

图G的一个正常边染色f,若满足:1)G中无2-色圈;2)对于V(G)中的任意两点u和v,有C(u)≠C(v),这里C(u)={f(uw)|uw∈E(G)},则f叫做图G的一个点可区别无圈边染色.图G的点可区别无圈边色数,记为χ′_(vda)(G),是图G的一个点可区别无圈边染色所用色的最小数目.证明了若图G是一个最小度不小于5,且顶点数不超过30Δ~4的图时,χ′_(vda)(G)≤10Δ~2,其中Δ是图G的最大度.     

图多彩染色中的2度点删除问题

对整数r0,图G的一个r-多彩染色是一个从顶点集V(G)到数集{1,2,…,k}的映射c,使得:(C1)相邻点获得的颜色不同;(C2)︱c(N(v))︱≥min{N(v),r}(其中N(v)代表v的邻点集)。使图G有一个正常的(k,r)-染色的最小k值称为G的多彩色数χ_r(G)。本文主要研究在图G中删掉任意一个2度点后多彩色数的变化。     

伞状树的奇强协调性

设G=V,E是一个简单图,若存在一个映射f:V(G)→{0,1,2,…,2|E|-1}满足(1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);(2)对任意的e1,e2∈E,若e1≠e2则g(e1)≠g(e2),此处g(e)=f(u)+f(v),e=uv,且{g(e)|e∈E}={1,3,5,…,2|E|-1},则称G是奇强协调图,f为G的奇强协调标号,讨论了一类树的奇强协调性.     

围长至少为6的曲面图的列表单射染色

图G的一个点染色称为单射染色,如果任何两个有公共邻点的顶点染不同的颜色.一个图G称为单射k-可选择的,如果对于顶点V(G)的任何一个大小为k的允许颜色列表L,都存在一个单射染色φ,使得对于v∈V(G),有φ(v)∈L(v).使得G为单射k-可选择的最小k,称为G的列表单射染色数,记作χ_i~l(G).设G是最大度为Δ,围长为g的可嵌入到欧拉示性数χ(Σ)≥0的曲面Σ的一个图.证明了若Δ≥7且g≥6,则χ_i~l(G)≤Δ+3.     

Hamilton连通的一个新的充分条件

设Ｇ是Ｋ－连通简单图（Ｋ≥３），若对任一Ｋ阶独立集Ｓ，ｕ，ｖ∈Ｓ，ｄ（ｕ）＋ｄ（ｖ）≥ｎ－１成立，则除一些例外图外，Ｇ是Ｈａｍｉｌｔｏｎ连通。     

几类图的负对控制数

设D V是图G=(V,E)的任意一个对控制集,如果一个函数f:V→{-1,0,1}满足条件1)对任意点v∈D,有f(v)=1,对任意点v∈V-D,有f(v)≤0,2)对任意点v∈V,均有f(N[v])≥1,则称函数f为图G的负对控制函数。负对控制函数f的重量f(V)是V中所有点的函数值之和,图G的负对控制数γp-(G)=min{f(V)|f是图G的负对控制函数}。本文研究一些图的负对控制数。