完全三部图K(n_1,n_2,n_3)的色唯一性

设G是简单图,用P(G,λ)表示图G的色多项式.若对任意简单图H使P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图.令K(n     

完全二部图的色性

设 G 是一个图,我们用 V(G)和 E(G)分别表示 G 的顶点集和边集,记 v=|V(G)|,ε=|E(G)|.P(G;λ)是图 G 的色多项式.称图 G 是色唯一的,如果任何图 H,由 P(H;λ)=P(G;λ),推知 H 与 G 同构.c_t(G)表示 G 中长为 k 的圈的个数.用G=(X,Y)表示二部图,K_(m,n)表示两部分的基数分别为 m 和 n 的完全二部图.本文中所有的图都是简单图,没有定义的术语和记号均可在[1]中找到.我们的主要结果是,用     

若干完全三部图的色唯一性

用P(G,λ)表示图G的色多项式.若对任意图H,当P(H,λ)=P(G,λ)时都有H和G同构,则称图G是色唯一的.给出了以下结果:m≥2且k≥0时,完全三部图K(m,m,m+k)是色唯一的;m≥2且m+1>k≥0时,完全三部图K(m,m+1,m+k)是色唯一的.     

一类完全三部图的色唯一性

用P(G,λ)表示简单图G的色多项式.设G是一个给定的简单图,若对任意简单图H,当P(H,λ)=P(G,λ)时都有H和G同构(记为H≌G),则称图G是色唯一的.本文证明了以下结果:设n,k,△都为非负整数,其中k≥0,△∈{4,5},若n≥1/3k~2+1/3△~2-1/3k△-1/3k-1/3△+4/3,则完全三部图K(n,n+△,n+k)是色唯一的.同时还给出了一个猜想.     

关于一类图K_n(1,m)的色性

一、引言本文考虑的图皆为有限,无向,无环的简单图.若两个图 G 与 H 有相同的色多项式,即 M_G(λ)=M_H(λ),则称 G 和 H 色等价.若由 M_H(λ)=M_G(λ)可推出 H 和 G 同构,则称 G 色唯一。     

关于完全t部图的色唯一性

设P(G,λ)是图的色多项式。如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.这里通过比较t 1色类的色划分数目,讨论了由Koh和Teo在文献[1]中提出的问题(若|ni-nj|≤2,当min(n1,n2,…,nt)充分大时,完全t部图K(n1,n2,…,nt)是否是色唯一图?)。改进了文献[5]中的结果。证明了若Σ1≤i≤ta2i=T,min{n a1,n a2,…,nt at,n-1}≥(T 1)/2,则K(n a1,n a2,…,n at)是色唯一图(其中ai是实数,n ai是正整数)。从而证明了若|ni-nj|≤k(i,j=1,2,…,t),min{n1,n2,…,nt}≥tk2/8 1,则K(n1,n2,…,nt)是色唯一图。     

包含圈的一些Ramsey数

用两种颜色,比如红和蓝,给完全图K_n的边着色.把着红色和蓝色的边集分别记为E_1和E_2,把K_n的边集分别是E_1和E_2的生成子图分别记为R和B,那么称R和B是K_n的一个分解,记为K_n=R⊕B.图G_1和G_2的Ramsey数,记为r(G_1,G_2),是使得K_n的任意一个分解K_n=R⊕B有R(?)G_1或B(?)G_2的最小正整数n.这里符号G(?)H表示图G包含子图H.此外,用C_n表示长为n的圈,GVH表示图G和H的联图.K_n表示n个相互独立的点,B_n指联图K_2     

一类完全三部图的K1,3-因子大集

令G是一个有限图,H是G的一个子图.若V(H)=V(G),则称H为G的生成子图.图G的一个λ重F-因子,记为Sλ(F,G),是G的一个生成子图且可分拆为若干与F同构的子图(称为F-区组)的并,使得V(G)中的每一个顶点恰出现在λ个F-区组中.一个图G的λ重F-因子大集,记为LSλ(F G),是G中所有与F同构的子图的一个分拆{B_i}_i,使得每个B_i均构成一个Sλ(F,G).当λ=1时,λ可省略不写.本文中,我们证明了当v≡4 mod 24时,存在LS(K1,3,Kv,v,v).     

完全二部图的K_(p,p)-分解大集的存在谱

令H,G是两个简单图,G是H的一个子图.H的G-分解,记为(λH,G)-GD,是指将图λH的所有边分拆为若干个与G同构的子图(称为G-区组).H的G-分解的大集,记为(λH,G)-LGD,是指图H的所有与G同构的子图的一个分拆Β_1,Β_2,…,Β_m,使得每个B_j(1≤j≤m)为一个(λH,G)-GD (称为小集).本文中,我们对完全二部图的K_(p,p)-分解的大集进行了研究,利用K_v的λ重K_κ-因子大集的存在性结果,采用直接构造的方法,得到了大集(λK_(m,n),K_(p,p))-LGD的存在谱,其中p为任意素数.     

关于完全t部图K(n1,n2,…,nt)的色唯一性

设P（G，λ）是图G的色多项式，如果对任意使P（G，λ）=P（H，λ）的图H都与G同构，则称G是色唯一图。这里通过比较图的特征子图的个数，讨论了由Koh和Teo在文献[1]中提出的问题（若｜ni-nj｜≤2，1≤i，j≤t且min{n1，n2，…，nt}充分大，K（n1，n2，…，nt）是否为色唯一图？）。证明了，若｜ni—nj｜≤2且t↑∑↑i=1 ni〉t^2/2＋t√t-1，则K（n1，n2，…，nt）是色唯一图；若αi=0或k，t↑∑↑i=1 n＋αi〉t^2k^2/8＋｜tk｜/2√t-1，则K（n＋α1，n＋α2，…，n＋αt）是色唯一图。其条件比文献[4]中的条件较好一些。     

单圈图的无符号拉普拉斯埃斯特拉达指数（英文）

设G是一个具有n个顶点的简单图.矩阵Q(G)=D(G)+A(G)表示图G的无符号拉普拉斯矩阵,其中D(G)和A(G)分别表示图G的顶点度对角矩阵和邻接矩阵.图G的无符号拉普拉斯埃斯特拉达指数定义为QEE(G)=∑_(i=1)~ne~(λ_i(G)),其中λ_1(G)≥λ_2(G)≥…λ_n(G)是指图G的无符号拉普拉斯特征值.本文确定了具有最大的无符号拉普拉斯埃斯特拉达指数的唯一的n个顶点的单圈图.     

5-桥图F(2,a,a,b,c)的色等价刻画

设P(G，λ)是图G关于变量λ的色多项式，P(G，λ)=P(H，λ)，称G和H色等价，由连接两个顶点的S条内部不交的路组成的图叫S-桥图。本讨论了5-桥图F(2,a,a,b,c)(c≥b≥a 1，a≥2)的色性，完整刻画了这类图的色等价图。     

两类完全三部图的图因子大集

令G是一个有限图,H是G的一个子图.若V(H)=V(G),则称H为G的生成子图.图G的一个λ重F-因子,记为S_λ(F,G),是G的一个生成子图且可分拆为若干与F同构的子图(称为F-区组)的并,使得V(G)中的每一个顶点恰出现在λ个F-区组中.一个图G的λ重F-因子大集,记为LS_λ(F,G),是G中所有与F同构的子图的一个分拆{B_i},使得每个B_i均构成一个S_λ(F,G).当λ=1时,λ可省略不写.在[Ars Combin.,2010,96:321-329]中已经得到了LS_λ(K_(1,2),K_(v,v))的存在谱.本文证明了当v≡4(mod 12)时,存在LS(F,K_(v,v,v)),这里F∈{K_(1,3),K_(2,2)}.     

完全二部图的Kp,p-分解大集的存在谱北大核心CSCD

令H,G是两个简单图,G是H的一个子图.H的G-分解,记为（λH,G）-GD,是指将图λH的所有边分拆为若干个与G同构的子图（称为G-区组）.H的G-分解的大集,记为（λH,G）-LGD,是指图H的所有与G同构的子图的一个分拆Β1,Β2,…,Βm,使得每个Bj（1≤j≤m）为一个（λH,G）-GD （称为小集）.本文中,我们对完全二部图的K（p,p）-分解的大集进行了研究,利用Kv的λ重Kκ-因子大集的存在性结果,采用直接构造的方法,得到了大集（λK（m,n）,K（p,p））-LGD的存在谱,其中p为任意素数.     

边着色路到完全图的嵌入

一、一个猜想设 P_n 为具有 n 个顶点的一条路,它的 n-1条边着上了不同的颜色,若这个着色能扩充为 n 个顶点的完全图 K_n 的一个正常的 x′(K_n)一边着色,则称边着色路 P_n 能嵌入于完全图.一般说来,设 G 是具有边色数 x′(G)的一个简单图,令 M(G)为 G 中所有满足以下性质的子图 H(?)G 的集合:存在 G 的一种正常的 x′(G)-边着色使得 H 的各条边具有不同的颜色.设 K_n 是 n 个顶点的完全图,把集合 M(K_n)简记为 M_n 于是我们一开始提出的问题“P_n 能否嵌入于完全图”等价于“P_n 是否属于 M_n”.     

不含三角形的图的λ3-最优性的充分条件

设G=(V,E)是一个连通图,边集S(?)E是一个3-限制性边割,如果G-S是不连通的并且G-S的每个分支至少有三个点.图G的3-限制性边连通度λ_3(G)是G中最小的一个3-限制性边割的基数.图G是λ_3(G)连通的,如果3-限制性边割存在.G是λ_3-最优的,如果λ_3(G)=ξ_3(G),其中ξ_3(G)=min{|[U,(?)]|:U(?)V,|U|=3 and G[U]是连通的).G[U]表示V的子集U的导出子图,(?)=V\U表示U的补.[U,(?)]是一条边的一个端点在U中另一个端点在(?)中的边的集合.本文给出了不含三角形的图是λ_3-最优的一些充分条件.     

q_k-树的色性

一、引言本文考虑的图都是有限、无向的简单图.设 V(G)为图 G 的点集,E(G)为图 G 的边集.对任意的正整数 q,称为 q-树的图是归纳定义的,最小的 q-树是完全图 k_q,一个n+1阶的 q-树(n≥q)是在任一个 n 阶的 q-树上添上一个新点,并且添上 q 条邻接这个点与 n 阶 q-树上任意选取 q 个两两相邻的点的边而获得.记 P(G,λ)为图 G 的色多项式     

完全图及完全二部图的点可区别Ⅳ-全染色

设G是简单图,图G的一个k-点可区别Ⅵ-全染色(简记为k-VDIVT染色),f是指一个从V(G)∪E(G)到{1,2,…,k}的映射,满足:()uv,uw∈E(G),v≠w,有,f(uv)≠f(uw);()u,V∈V(G),u≠v,有C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.数min{k|G有一个k-VDIVT染色}称为图G的点可区别Ⅵ-全色数,记为x_(vt)~(iv)(G).讨论了完全图K_n及完全二部图K_(m,n)的VDIVT色数.     

子图匹配数与图无符号拉普拉斯谱(英文)

设H是图G的一个子图.图G中同构于H的点不交的子图构成的集合称为G的一个H-匹配.图G的H-匹配的最大基数称为是G的H-匹配数,记为ν(H,G).本文主要研究ν(H,G)与G的无符号拉普拉斯谱的关系,同时也讨论了ν(H,G)与G的拉普拉斯谱的关系.     

包装{(p,p-1),(p,p)}图对和 Slater 问题

设 G 是一个简单无向图.V(G),E(G)分别表示 G 的顶点集和边集.(?)表示 G 的补图.我们以 S_(?) 表示 n 1阶星图 k_(1,n-1).称 G 是(p,p—k)图,如果|E(G)|=|V(G)|—k.称|V(G)|为图 G 的阶.设 G_1,G_2是同阶图,(?)_1是 V(G_1)到 V(G_2)的一个双射,(?)_2是 V(G_2)上的一个置换,我们用(?)_2(?)_1表示 V(G_1)到 V(G_2)的双射,其作用为