P■形图的伴随多项式的分解及其补图的色等价性

设P_n和C_n是具有n个顶点的路和圈,nG表示n个图G的不相交并。令S~*_(r(m+1)+1)表示rP_(m+2)的每个分支的一个1度点重迭后得到的图,E■表示把P_m的一个1度点与S~*_(r(m+1)+1)的r度点重迭后得到的图,可简记为E■,δ=(r+1)m+r;设n(≥3)是奇数,λ=n+2~(-1)(n+1)δ,图P■表示把2~(-1)(n+1)E■的每个分支的r+1度顶点分别与P_n的下标为奇数的2~(-1)(n+1)个顶点重迭后得到的图,运用图的伴随多项式的性质,讨论了图簇E■∪rK_1、P■∪K_1和P■∪E■的伴随多项式的因式分解式,令n=2~(k-1)q-1,λ_k=(2~kq-1)+2~(k-1)qδ,讨论了图簇P■和P■∪(k-1)K_1的伴随多项式的因式分解式,进而证明了这些图的补图的色等价性。     

Ramsey定理的一种推广

Ramsey定理指出:对于任何一个正整数k,存在一个最小的正整数r(k,k),使得对任意一个至少有r(k,k)个顶点的图G,它或者有k个顶点的完全子图Kk,或者有k个顶点是独立集.由此定理易得:设G是顶点数n>r(k,k)的简单图,其边数e>0,且G的所有k阶导出子图的边数相等,那么G是完全图.并给出上述结论的推广:设G是n(n≥4)阶简单图,其边数e>0,对某个给定的自然数k(2≤k≤n-2),若G的所有k阶导出子图的边数相等,则G是完全图.     

关于图的边着色的一个猜想

若G是简单图,v(G)是偶数,χ'(G)=?(G)+1,则存在点v∈V(G),使χ'(G-v)=χ'(G)=?(G)+1.本文对此进行了研究,当图G满足以下条件之一时:(1)设G是含有割边的连通图,χ'(G)=?(G)+1;(2)设G是连通图,κ'(G)=2,G中最多除两个2度顶点外,其它顶点的度数均为k(k2),v(G)=2n+2,χ'(G)=?(G)+1;(3)设图G是k正则图,v(G)=2n+2,χ'(G)=?(G)+1;(4)设图G是有2n+2个顶点的连通图,且除点v的度小于k外,其它顶点的度都等于k,χ'(G)=?(G)+1;(5)设图G是有2n+2个顶点的连通图,且除点u,v,d(v)d(u)k外,其它顶点的度都等于k,χ'(G)=?(G)+1;此猜想也是成立的.     

基回数为2的自中心图

Buckley 指出找寻自中心图的特征是一个困难的任务.作为这一工作的开始,找出一些自中心图类看来非常必要.文[1]定理3中证明当 k=■或 n≤k≤[(1/2)n(n-1)]时,n 个顶点 k 条边的自中心图存在.本文建议以基回数为出发点构造自中心图,并确定了基回数为2,即 k-n=1的全部自中心图.本文还纠正了[1]中的一个疏忽.设 G=(V,E)是简单图,u,v∈V(G),d(u,v)为 u,v,两点的距离.定义1 图 G 的半径 r(G)=(_{(v,w)}定义2 图 G 中顶点“的最远距离     

一类树的伴随多项式的分解及其补图的色等价性

设Pn和Cn是具有n个顶点的路和圈,nG表示n个图G的不相交并。令S*r（m+1）+1表示rPm+2的每个分支的一个1度点重迭后得到的图,E■表示把Pm的一个1度点与S*r（m+1）+1的r度点重迭后得到的图,可简记为E■,δ=（r+1）m+r;设n（≥4）是偶数,λ=（n+1）+2-1（n+2）δ,令图P■是表示把2-1（n+2）E■的每个分支的r+1度顶点分别与Pn+1的下标为奇数的2-1（n+2）个顶点重迭后得到的图,运用图的伴随多项式的性质,讨论了图簇E■∪rK1、P■∪E■和P■∪2E■∪rK1的伴随多项式的因式分解式,进而证明了这些图的补图的色等价性。     

路图P3(G)的色数

设G是一个图,G的路图P3(G)的顶点集是G中所有三个顶点的路P3, 当G中的两个P3路形成P4路或C3圈时,在P3(G)中它们所代表的两个顶点相邻. 在这篇文章中,我们得到对于一个无三角形的图G, χ(P3(G))≤β(G),其中β(G)表G的点覆盖数. 对于顶点数至少为3的连通图G,χ(P3(G))≤2当且仅当G是二部图, 并且χ(P3(G))=1当且仅当 G是星图. 对于K4的剖分图G,2≤χ(P3(G))≤3. 对于系列平行图和外可平面图G,χ(P3(G))≤3.     

关于中间图补图的一个定理的简单证明

对于图G,定义它的中间图M(G)的顶点集为V(G)∪ E(G),顶点集中的两点x和Y在M(G)中相邻当且仅当{x,y}∪ E(G)≠φ,并且x和y在G中相邻或者关联.在这篇文章中简化了下面这个最近已经得到的定理的证明,即一个图G的中间图M(G)的补图是哈密顿的当且仅当G不是星图,并且G不同构于{K1,2K1,K2,K2 ∪ K1,K3,K3 ∪ K1}中的任意一个图.     

M(o)bius梯子的L(d,1)-标号

对给定的正整数d,图G的L(d,1)-标号是从V(G)到非负整数的函数,且满足:任意两个相邻顶点的标号差至少为d,而且距离为2的任两个顶点的标号至少为1.L(d,1)-标号的跨度是标号差的最大值.G的L(d,1)-标号数是G的所有L(d,1)-标号的最小跨度.本文完全给出了M(o)bius梯子的L(d,1)-标号数.     

若干图的伴随分解及色等价性

设Pm和Cm分别表示具有m个顶点的路和圈,G是任意的r阶连通图,设m是正奇数,把路Pm的标号为奇数的2-1(m+1)个顶点分别与2-1(m+1)G每个分支的第i个顶点Vi重迭后所得到的图记为ρG(i)m+2-1(m+1)r。运用图的伴随多项式的性质,首先给出了一类图簇ρG(i)(2 m+2)+((m+1)r的伴随多项式。进而令m=2t-1 q-1,λn=(2nq-1)+2n-1 qr,在讨论上述图的伴随多项式的基础上,我们证明了图ρG(i)λt和ρG(i)λt∪(t-1)K1的伴随多项式的因式分解定理,进而证明了这些图类的补图的色等价性。     

完全三部图的点可约全染色

设f:V(G)∪E (G)→{1,?,k}是图G的一个(非正常)k-全染色,其中1≤k≤Δ+1。若对任意两个顶点u,v∈V (G)且d (u)=d (v)时,满足S (u)=S (v),则称f是图G的一个点可约k-全染色,其中S(u)表示顶点u和点u的关联边上分配的颜色组成的色集合。运用图的色集合事先分配法、组合分析法和构造染色法,结合完美匹配探讨了完全三部图K_m,n,p的点可约全染色问题,进一步确定了K_m,n,p的点可约全色数。     

连通图顶点集的一种划分

1.引言设G=(X,E)为有限阶的简单图,X与E分别为G的顶点集与棱集。在下文中,我们总假定G是连通的。以d(x,y)表示G的两个顶点x,y之间的距离。对于每个x∈X,定义x的“联系数”(associated number)为     

两类E~G形图簇的补图的色等价性定理

设G是任意的p阶连通图,用ΨG(i)(k,p)表示把图G的第i个顶点vi与星图Sk+1的k度点重迭后得到的图(1≤i≤p),给出了图ΨG(i)(k,p)与星图Sn+1组合而成的两类EG形图簇,并通过研究这些图簇的伴随多项式的因式分解,进而证明了它们的补图的色等价性定理。     

优美图中Rosa定理的两个推广

假如对于简单图 G(V,E)的vu∈V,赋以一个非负整数φ(u),则称图 G 是标定的,(v)称为顶点 V 的标数,并以|(u)-(v)|作为棱 uv 的标数,简记作(uv).定义若图 G(V,E)有满足下列条件的标数法,则称 G 是优美图(graceful graph):(1)对于 u,v∈V(G),当 u≠v 时,(u)≠(v);(2)max(u)=|E(G)|u∈V(3)对于“uv∈E,xy∈E,只要 uv≠xy,则有|(u)-(u)|≠|(x)-(y)|.在优美图的理论中有如下结果:定理(Rosa)完全二部分图是优美图.本文给出这个定理的两个推广.     

114—三次图的构造

在[1]中,只讨论了不含三角形时abc为111和222两种情况的abc—三次图,本文的目的是解决114—三次图的存在问题,并且给出一个图是114—三次图的充要条件,它类似于[1]中的定理4,但不必给予“无三角形”的限制。我们用G表示一个连通的无自环的非K_4的三次图,H表示G的一个最大二部分子图,H中的一条路如果满足(ⅰ)非平凡(ⅱ)它的端点在H中为3度(ⅲ)所有其它顶点在H中为2度,则称这样的一条路为H的一条初等路。如果G的最大二部分子图日中每个3度顶点是长度分别为a、b、c的三条初等路的公共端点,则称G为abc—三次图,若S是G的顶点集V(G)的一个子集,则K=[S,]表示G的棱集E(G)的一个子集,它的端点一个在S中,另一个在中,且称K为G的棱截。截指标c(K,H)定义为:     

Brooks定理的附注

<正> 图的顶点的染色是图论中的重要问题之一。本文从讨论图的色数的上界问题,从而得出Brooks定理的又一证明。1.基本概念如果用颜色去染一个图G的顶点,使得任意有棱相连的两个顶点均有不同的颜色。这样     

Cartesian积的局部边-路替换图的L(2,1)-标号

设d为正整数,图G的一个L（d,1）-标号就是从非负整数集到V（G）的一个函数,且使得2个相邻顶点的标号相差至少是d,2个距离为2的顶点的标号相差至少为1. 图G的L（d,1）-标号的跨度就是所有L（d,1）-标号的最大值和最小值之差. 图G的L（d,1）-标号数是G的所有L（d,1）-标号下跨度的最小值. 在已有研究图G的边-路替换图的L（d,1）-标号基础上,研究了Cartesian积的局部边-路替换图的L（2,1）-标号.     

Y2,2,λ*形树的伴随多项式的分解及其补图的色等价性

设Pn和Cn是具有n个顶点的路和圈,nG表示n个图G的不相交并。令S*r（m+1）+1表示rPm+2的每个分支的一个1度点重迭后得到的图,■表示把Pm的一个1度点与S*r（m+1）+1的r度点重迭后得到的图,可简记为■,δ=（r+1）m+r;设n（≥3）是奇数,λ=n+2-1（n+1）δ,图■表示把■的每个分支的r+1度顶点分别与Pn的下标为奇数的2-1（n+1）个顶点重迭后得到的图,Y*（2,2,2λ+1）表示把■的两个r+2度点分别与2P3的两个2度点重迭后得到的图,运用图的伴随多项式的性质,讨论了图簇■和■的伴随多项式的因式分解式,令n=2k-1q-1,λk=（2kq-1）+2k-1qδ,讨论了图簇Y*（2,2,λk）∪K1和Y*（2,2,λk）∪（k-1）K1的伴随多项式的因式分解式,进而证明了这些图的补图的色等价性。     

Mobius梯的(d,1)-全标号

图G 的(d,1)-全标号是从V(G)∪E(G)到非负整数的函数,且满足：(i) G中任意2个相邻顶点的标号不同;(ii) G中任意2个相邻边的标号不同;(iii) 顶点与其关联边的标号差至少为d.(d,1)-全标号的跨度是标号差的最大值. G 的(d,1)-全标号数是G的所有(d,1)-全标号的最小跨度,记为λ^T_d(G).本文完全给出了Mobius梯的(d,1)-全标号数.     

若干运算图的倍乘赋权Harary指标（英文）

ALIZADEH等近期提出了一个修正的Harary指标,即顶点对的贡献被赋予其度的乘积.其指标被称为倍乘赋权Harary指标,定义为H_M(G)=∑u≠vδ_G(u)δ_G(v)/d_G(u,v),其中,δ_G(u)表示顶点u在图G中的度,d_G(u,v)表示2个顶点u和v在图G中的距离.给出了张量积G×K_r,强积G■K_r,圈积G_1oG_2的倍乘赋权Harary指标值的精确计算公式,这些公式与图的其他不变量(如倍加赋权Harary指标、Harary指标、第1类和第2类Zagreb指标、第1类和第2类反Zagreb指标)有关.此外,利用所得结果计算了开栅栏与闭栅栏的倍乘赋权Harary指标.     

s-点连通图的路可扩性(英文)

设G是一个简单图.如果G的每一个有s个点的导出子图都连通,但存在一个s-1个点的导出子图不连通,则称G是s-点连通的,其中s≥3.一条路称为可扩的,如果存在路P′满足V(P′)V(P)且|V(P′)|=|V(P)|+1.一个图称为完全路可扩的,如果它的直径至多为2且它的每一条少于|V(G)|个顶点的路都是可扩的.本文证明了s-点连通图,如果它的顶点数n与s满足n≥2s-1,则它是完全路可扩的.