正则图的代数连通度

设G=(V,E)是一个具有n个顶点的简单图,A(G)是G的邻接矩阵,D(G)表示G的度对角矩阵,图G的拉普拉斯矩阵定义为L(G)=D(G)-A(G).若矩阵L(G)的特征值为μ1≥μ2≥…≥μn-1≥μn=0,则称μn-1为G的代数连通度.研究了正则图的代数连通度,得到了下列结论:μn-1≤(nrln(n-l))/(6n-8-4r-nln(n-1))这里,r表示正则图的度.     

Ln,p图的代数连通度

Kp表示p阶完全图.选取Kp的任意r个顶点分别点粘接r棵树,得到n阶图Ln,p.所有n阶图Ln,p的集合记为（L）n,p.代数连通度是刻画图的连通性的重要参数,笔者分别确定了Ln,p中具有最大、最小和第二小代数连通度的图.     

由轮生成的Cayley图的广义3-连通度

令S?V(G),κ_G(S)表示图G中内部不交的S-树T_1,T_2,…,T_r的最大数目r,使得对任意i,j∈{1,2,…,r}且i≠j,有V(T_i)∩V(T_j)=S,E(T_i)∩E(T_j)=?.定义κ_k(G)=min{κ_G(S)|S?V(G),且|S|=k}为图G的广义k-连通度,其中k是整数,且2≤k≤n.令Sym(n)是在{1,2,…,n}上的对称群,T是Sym(n)的对换集合.G(T)表示点集是{1,2,…,n},边集是{ij|(ij)∈T}的图.若G(T)是一个轮图,则将Cayley图Cay(Sym(n),T)简记为WG_n.主要研究由轮生成的Cayley图WG_n的广义3-连通度,并证明κ_3(WG_n)=2n-3,其中n≥4.     

泡序图的广义4-连通度

S?V(G)是G的一个顶点集且|S|≥k,其中2≤k≤n.连接S的树T叫作斯坦纳树.两棵斯坦纳树T₁和T₂称为内部不交的,当且仅当它们满足E(T₁)∩E(T₂)=?和V(T₁)∩V(T₂)=S.令κ_G(S)是G内部不交的斯坦纳树的最大数目,κ_k(G)=min{κ_G(S)∶S?V(G),|S|=k}定义为G的广义k-连通度.很显然,当|S|=2时,广义2-连通度κ₂(G)就是经典连通度κ(G).因此广义连通度是经典连通度的推广.主要讨论泡序图B_n的广义4-连通度κ₄(B_n).得到的结论是当n≥3时,κ₄(B_n)=n-2.     

一些笛卡尔乘积图的限制连通度

子集S(∩)V(G)称为限制割,若任何点v∈V(G)的邻点集NG(v)都不是S的子集且G-S不连通.若G中存在限制割,则定义限制连通度κ1(G)=min{| S|S是G的一个限制割}.考虑了笛卡尔乘积图,证明了设G=G1×G2×…×Gn,若Gi是满足某些给定条件的ki连通ki正则且围长至少为5的图,其中i=1,2,…,n,则κ1(G)=2n∑i=1ki-2.     

Nordhaus-Gaddum型的代数连通度的界

对任一个n阶单图G,用a(G)表示G的代数连通度,Gc为G的补图.通过代数连通度与Laplacian谱半径的关系,给出了几类图的Nordhaus-Gaddum的代数连通度的和的界.     

折叠超立方体的广义3-连通度

设图G是一个连通图,S⊆V(G)。图G的一棵S-斯坦纳树是一棵包含S中所有顶点的树T=(V ',E '),使得S⊆V '。如果连接S的两棵斯坦纳树T和T ',满足E(T)∩E(T ')=且V(T)∩V(T ')=S,则称T和T '是内部不交的。定义κ(S)为图G中内部不相交S-斯坦纳树的最大数目。广义k-连通度(2≤k≤n)定义为κ_k(G)=min{κ(S)|S⊆V(G)且|S|=k},显然,κ₂(G)=κ(G)。证明了κ₃(FQ_n)=n,其中FQ_n是n-维折叠超立方体。     

每点都与3度点相邻的最大临界3棱连通图的结构

没G=(V,E)是3棱连通图,若对每个x∈V(G),G-x 不是3棱连通的,则称G 为临界3棱连通图.p 阶临界3棱连通图的全体记为(?)_3(p),G∈(?)_3(p)称为最大的,如果不存在H∈(?)_3(p),使|E(H)|>|E(G)|.本文给出每个点都与3度点相邻的p 阶最大临界3棱连通图的结构.     

关于图的代数连通度的注记

n阶连通图G的代数连通度、点连通度和边连通度分别记作α(G) ,κ(G)和λ(G) .本文给出了当 2 κ(G) n- 2时 ,α(G) =κ(G)成立的充要条件 ,讨论了α(G)的代数重数以及相应于特征值α(G)的特征向量的性质 .最后给出了当 1 λ(G) n- 2时 ,α(G) =λ(G)的充要条件 .     

双圈图的N-G型的代数连通度的界

对任一个n阶单图G,用a(G)表示G的代数连通度,GC表示它的补图.针对双圈图,即边数等于顶点数加1的且只含有2个边不交的基本圈的简单连通图,证明了对任一n阶双圈图G,有1≤a(G)+a(GC),当且仅当G≌G1时等式成立.     

可平面图3可选择的一个充分条件

给G=(V,E)的每个顶点分配一个色列表L={L(v)|v∈V},若G有一个正常顶点染色φ,使得对每个顶点v∈V,都有φ(v)∈L(v),则称G是L可染的。若对G的每一个满足|L(v)|≥k,v∈V的L,G都是L可染的,则称G是k可选择的。本文通过权转移方法证明了每个不含4,6,8,10圈的可平面图是3可选择的。     

图的子图中(n,r)-正交因子分解

设图G的顶点集为V(G)，边集为E(G)，g和f是定义在V(G)上的2个整值函数，满足对于一切x∈V(G)，g(x)≤f(x).若G是一个(mg+rn，mf-rn)-图，1≤n＜m，r≥2，且对于x∈V(G)，有g(x)≥k≥1，则存在G的一个子图G′，使得G′具有一个(f，g)-因子(n，r)-正交于G的任意给定子图H，其中｜E(H)｜=nk.     

图K_(2n)\E(F_5)(n≥13)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K2n\E(F5)(n≥13)的点可区别边色数.     

含有割点的图的测地集

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

一类哈密顿图的控制数的上界

设G=(V,E)是一个简单图,D是V的一个子集,如果集合V-D的任意点都与D中的点相邻,则称D为图G的一个控制集.图G的最小控制集中的点数称为G的控制数.本文对哈密顿图的控制数进行了研究,证明了命题:如果n阶图G是一个最小度为5的哈密顿图,则图G的控制数就不大于5n/14.     

图K2n\E（Fm）（n≥4,m≥2）的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K2n\E(Fm)(n≥4,m≥2)的点可区别边色数.     

图的强直积的2-距离染色(英文)

设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。     

图的扩展离心连通指数(英文)

设图G=G(V,E)是简单图.图扩展离心连通指数Aζc(G)是基于邻接和的指数,即Aζc(G)=∑u∈V(G)(ΠV∈N(u)dv)/e(u)其中e(u)为图顶点u的离心率,N(u)为顶点u的邻点集.本文刻画了树中具有最大、第二大、最小、第二小扩展离心连通指数的树的特征和单圈图中具有最大扩展离心连通指数的单圈图的特征.     

关于哈密尔顿指数的综述

图G的线图L（ G）是指以G的边集E（ G）为顶点集且L（ G）的2个顶点邻接当且仅当它们在G中有公共顶点。 n次迭代线图Ln（G）递归地定义为L0（G）=G,Ln（G）=L（Ln-1（G））（n∈N=｛0,1,2,…｝）,其中L1（ G）=L（ G）并且假设Ln-1（ G）非空,使得Ln（ G）是哈密尔顿的最小整数n称为哈密尔顿指数,用h（ G）表示。该文综述了（类）哈密尔顿指数的一些结果。