临界κ连通图中的点度数

如果在—个κ连通图G中删掉任意一个顶点后得到的图都不再是κ连通,则称G为临界κ连通.Chartrand,Kaugars和Lick证明了每一个临界κ连通图(κ≥2)都含有一个度数小于(3κ-1)/2的顶点.Hamidoune进一步证明了每一个临界k连通图都至少含有两个这样的顶点,并且这一下界是最优的.在本文中,我们证明如果一个临界κ连通图恰好含有两个度数小于(3κ-1)/2的顶点,则这两个顶点的度数一定是κ.     

E~(G(i))类图簇的伴随多项式的因式分解及色性分析

设Sn+1是n+1个顶点的星图,G是任意的p阶连通图.ΨG(i)(n,p)表示把Sn+1的n度点与G的第i(1 i p)个顶点重迭后得到的图;ErG(p+i)(r-1)表示把rG的r-1个分支的第i个顶点依次与Sr的r-1个1度点邻接,同时把剩下的一个图G的第i个顶点与Sr的r-1度点重迭后得到的图.我们通过讨论图簇ErG(p+i)(r-1)∪(r-1)K1的伴随多项式的因式分解,证明了它的补图的色等价图的结构性质.     

路和平方路笛卡尔乘积图的r-多彩着色（英文）

图G的r-多彩k-着色是图G的一个正常k-着色,并满足G中的每一个顶点的邻点的颜色数至少为这个顶点的度d(v)和r的最小值.使得图G具有r-多彩k-着色的最小整数k称为图G的r-多彩色数,用X_r(G)表示.本文研究了路和平方路的笛卡尔乘积图的r-多彩着色,得出了其r-多彩色数的确切值.     

点可迁图的限制边连通度

设S是连通图G的边子集.如果G-S不连通而且不含孤立点,那么称S是G的一个限制边割.G中所有限制边割中最小边数称为G的限制边连通度,记为′(G).限制边连通度是对传统边连通度的推广,而且是计算机互连网络容错性的一个重要度量.点可迁图是一类重要的网络模型.本文证明了如下结论 设G是连通的点可迁图.如果G的点数n4,而且点度k2,那么或者′(G)=2k-2,或者n是偶数,G含三角形且存在整数m2,使得k′(G)=n/m2k-3.     

两类网络的2-限制连通度

给定图G=(V,E)和非负整数h,图G的h-限制点割S是V(G)的一个子集(如果存在)使得G-S不连通且G-S中任一点的度数至少为h.图G的h-限制连通度κ~h(G)是G的最小h-限制点割的阶数.本文中,我们证明了κ~2(FCQ_n)=4n-4 (n≥8),κ~2(SQn)=4n-8(n≥4),其中FCQ_n和SQ_n分别是n维折叠交叉超立方体和n维spined cube.     

强定向图的k-强距离

对强连通有向图D的一个非空顶点子集S,D中包含S的具有最少弧数的强连通有向子图称为S的Steiner子图,S的强Steiner距离d(S)等于S的Steiner子图的弧数. 如果|S|=k, 那么d(S)称为S的k-强距离. 对整数k≥2和强有向图D的顶点v,v的k-强离心率sek(v)为D中所有包含v的k个顶点的子集的k-强距离的最大值. D中顶点的最小k-强离心率称为D的k-强半径,记为sradk(D),最大k-强离心率称为D的k-强直径,记为sdiamk(D). 本文证明了,对于满足k+1≤r,d≤n的任意整数r,d,存在顶点数为n的强竞赛图T′和T″,使得sradk(T′)=r和sdiamk(T″)=d;进而给出了强定向图的k-强直径的一个上界.     

含有给定k-正则子图的[a,b]-因子

设G是一个图,并设n,k,r,a和b是整数且满足k≥1,k≤a＜b和n≥3.对于G的给定的k-正则图H,如果G是K1,n-free图,且G的最小度至少是((n(a+1)+b-a-(k+1))/(b-k))「(ab+b-a-k)/(2(n-1))」-(n-1)/(b-k)(「(an+b-a-k)/(2(n-1))」)2-1,那么G有一个[a,b]-因子F使得E(H)(∈)E(F).类似地,也得到了关于图G有一个r-因子含有G中给定的k-正则子图的度条件.进一步,指出这些度条件是最佳的.     

笛卡尔乘积图的圈点连通度

图G的圈点连通度,记为κ_c(G),是所有圈点割中最小的数目,其中每个圈点割S满足G-S不连通且至少它的两个分支含圈.这篇文章中给出了两个连通图的笛卡尔乘积的圈点连通度:(1)如果G_1≌K_m且G_2≌K_n,则κ_c(G_1×G_2)=min{3m+n-6,m+3n-6},其中m+n≥8,m≥n+2,或n≥m+2,且κ_c(G_1×G_2)=2m+2n-8,其中m+n≥8,m=n,或n=m+1,或m=n+11;(2)如果G_1≌K_m(m≥3)且G_2■K_n,则min{3m+κ(G_2)-4,m+3κ(G_2)-3,2m+2κ(G_2)-4}≤κ_c(G_1×G_2)≤mκ(G2);(3)如果G_1■K_m,K_(1,m-1)且G_2■K_n,K_(1,n-1),其中m≥4,n≥4,则min{3κ(G_1)+κ(G_2)-1,κ(G_1)+3κ(G_2)-1,2_κ(G_1)+2_κ(G_2)-2}≤κ_c(G_1×G_2)≤min{mκ(G_2),nκ(G_1),2m+2n-8}.     

关于极大外平面图的度偏差的极值

设G是一个由n个顶点,m条边构成的简单连通图.如果图G所有顶点的度相同,则我们称图G是正则图,反之,称图G是不规则图.对于一个不规则图G,由其不变量定义的度偏差为s(G)=∑_(i=1)^(n)|d_(i)-2m/n|,其中d_(i)表示G的第i个顶点的度.本文给出极大外平面图的度偏差的极大值和极小值,并刻画其对应的极值图.     

单圈图的代数连通度的排序

n阶图G称为是一个单圈图,如果G是连通的,并且G的边数也是n.用U(n)表示所有n阶单圈图所成的集合.给出了当阶数n≥25时,代数连通度为前九大的n阶单圈图及它们的代数连通度.