类整图

图G是一个简单图,图G的补图记为(G).如果G的谱完全由整数组成,我们就说G是整图.如果(aKa∪βKb)是整图,我们将讨论它是具有如下形式的一种整图[kt/τx0+mt/τz]K(t+ln)k+lm∪[kt/τy0+(t+ln)k+lm/τz]nKlm其中各参数满足的条件见文中定理.     

↑——αKα∪βKb类整图

图G是一个简单图，图G的补图记为↑-G．如果G的谱完全由整数组成，我们就说G是整图．如果↑--αKαUβKb是整图，我们将讨论它是具有如下形式的一种整图↑——[kt/τx0＋mt/τz]K（l＋ln）k＋ln∪[kt/τy0＋（t＋ln）k＋lm/τz]nKlm其中各参数满足的条件见文中定理。     

k-连通[k+3,k]-图中的Hamilton路

如果G的任意s个点的导出子圈中至少含有t条边,则称图G为[s,t]-图.本文证明了若G是k-连通[k+3,k]-图(k≥2),则G或者含有Hamilton路或者同构于Kk+2∨ Gk(其中Gk是含有k个点的任意图).     

完全三部图K(n-k,n-v,n)的色唯一性

设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(GH),则称图G是色唯一图.文献[Lau G C,Peng Y H.Chromatic uniqueness ofcertain complete tripartite graphs.Acta Mathematica Sinica,English Series,2011,27(5):919-926]中提出一个猜想(若k≥v≥2,n≥k2/4+v+1,则完全三部图K(n-k,n-v,n)是色唯一的),并证明了若2≤v≤4,k≥v≥2,n≥k2/4+v+1,则K(n-k,n-v,n)是色唯一的.通过比较三角形子图和无弦四边形子图的个数,证明了若v≥4,k≥2v2+4,n≥(k+2)2/8+3,则K(n-k,n-v,n)是色唯一图。     

圈的幂图的s-迹连通性

对于图G的任意两个顶点x和y,如果G有一条(x,y)-生成迹,则称图G是迹连通的.给定一个整数s≥0,对于任意点子集X?V(G)并且|X|≤s,如果G-X是迹连通的,则称图G是s-迹连通.设k是一个正整数,图G的k次幂图记为Gk.设t(G)是t一个最大值s使得图G是s-迹连通但不是(s+1)-迹连通,设Cn是一个包含n...     

k-连通的强-［k+4,2］图的Hamilton路

如果G的任意s个点的导出子图中至少含有t条独立边,则称图G为强-［s,t］图。本文证明了以下结果：设G是k-连通的强-［k+4,2］图,且δ≥k+1,则G或者有Hamilton路或者同构于(∪^k+2_i=1H_i)∨G_k,其中H_i≌K₂,i=1,2…k+2,G_k是含有k个点的任意图。     

一类整函数的分解

本文讨论具有如下形式的整函数的分解性 H(z)+zexp((2nπi/τ)z+G(z)),其中H(z)和G(z)都是以为τ周期的整函数。找出了一些素整函数,其各阶导函数都是素的。     

图Kn-E(Kr),Kr(∪)Kn的整和数

Z表示所有整数的集合.一个有限子集S(∪)Z上的整和图是指图(S,E)中uv∈E当且仅当u+v∈S.图G是整和图,如果它同构于某个子集S(∪)Z上的整和图.图G的整和数是指使(G∪mK1)成为一个整和图时加入的孤立顶点的最少个数m.1994年Harary在[3]中提出了4个未决的问题,本文完整地回答了其中的第一个问题,即确定了图(Kn-E(Kr))的整和数.具体结论如下:ζ(Kn-E(Kr))={0(r=n,n-1)n-1(n-2≥r≥[2n/3]-1)3n-2r-4([2n/3]-1＞r≥n/2)2n-4([2n/3]-1＞n/2≥r≥2)其中n≥5,r≥2,[x]表示不小于x的最小整数.     

图的邻域并和连通的[k,k+1]-因子

设G是阶为n的图.F是G的支撑子图且对所有的x∈V(G)都有k≤dF(x)≤k+1,则称F为G的[k,k+1]-因子.一个[k,k+1]-因子如果连通,则称为连通的[k,k+1]-因子.一个[k,k+1]-因子若包含一个哈密顿圈,则称为哈密顿[k,k+1]-因子.给出了图有哈密顿[k,k+1]-因子或连通的[k,k+1]-因子关于邻域并的若干新的充分条件.     

恰有2个内度的2维Torus网络的定向图

设G是一个简单图且D是G的一个定向图.若对D中任意顶点x,d-(x)=a或b,则称G是[a,b]可实现的.主要研究了2维Torus网络中[a,b]可实现的充要条件.设H=Torus(p,k)是一个2维Torus网络,其中p和k是2个不小于3且奇偶性相同的正整数.设0≤a,b≤4,则H是[a,b]可实现的当且仅当存在非负整数s和t使得s+t=kp且as+bt=2kp.     

Sampathkumar猜想的证明

设x_k(G)表示图G 的P_k-色分划数,本文证明了Sampathkumar 等在文献[2]中提出的一个猜想,即对任何P 阶图G,都有X_k(G)+X_k(■)≤t+1,X_k(G)+X_k(■)≤((t+1))/2)~2,这里t={p/k}.     

完全t部图K(n-k,n-2,n,…,n)的色唯一性

文章介绍了完全t部图K(n-k,n-2,n,…,n)的色唯一性,设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图,通过比较t部图的t+1色类的划分数和三角形子图的个数证明,如果n>[(k+1)2/4]+1,并且k>2,则完全t部图K(n-k,n-2,n,…,n)是色唯一图。     

判断k-可序哈密顿-连通图的新条件

具有n个顶点的图G(n≥3)是k-可序哈密顿-连通的(k是整数,且2≤k≤n),如果对于G中每一个具有k个不同顶点的可序集合S={v1v2,…,vk},都存在G中的哈密顿路P包含S且不改变其中元素的次序.本文证明了:对于具有n个顶点的图G,u、v是G中任意两个不相邻的顶点,且d(u)+d(v)≥n+1.如果G是「k+1/2﹁-连通的k-可序图,k是整数且2≤k≤n/12,则G是k-可序哈密顿-连通图.     

（a，b，k）-临界图的两个充分条件

设G是一个n阶图，1≤a相似文献   

最小度与[a,b]-k-对等图

设G=(V(G),E(G))是一个n阶图,1≤an+(a+b)-2■bn-2k+1,则G是[a,b]-k-对等图。推广了已有的结果。     

一类整数距离图的分数色数

利用整数距离图的结构特征,研究当m<2k时,G(Z,Dm,k,t)的分数色数(其中Dm,k,t={1,2,…,m}-{k,k+1,…,k+t}),并给出在k>t,m≥2k条件下G(Z,Dm,k,t)的分数色数,以及当k>t,m=2k+i,0≤i≤2t-1时,G(Z,Dm,k,t)的色数.     

图与其补图谱半径之和的新上界

该文给出了图与其补图谱半径之和ρ(G)+ρ(Gc)的新上界,对任一n阶图G,有:p(G)+p(GC)≤((2-1/t)n(n-1))和p(G)+p(GC)≤((2-1/T)n(n-1))其中t=min{k,(k-)},T=max{k,(k-)},k,(k-)分别为图G和其补图Gc的色数.从而改进了[6],[8],[10]的结果.     

图的独立数与分数一致性

设G是一个顶点集为V(G),最小度为δ(G),独立数为α(G)的图,k≥2是整数。图G的支撑子图F称作是图G的分数k-因子,如果对于每一个x∈V(F)都有dh G(x)=k。如果对于图G的每条边e,图G都有一个分数k-因子包含它而且同时有一个分数k-因子不包含它,则称图G为分数k一致图。证明了如果δ(G)≥k+2,且α(G)≤4k(δ-k-1)/(k+1)2,则图G是一个分数k一致图。     

韧度与分数(k,n′)-临界消去图

设G是一个图,若去掉G中的任意n′个顶点的剩余子图仍是分数k-消去图,则称G是一个分数(k,n′)-临界消去图.文章证明了当t(G)≥((k2-1)(n′+1))/k,且n>k+n′+1时,G是分数(k,n′)-临界消去图.     

非连通图(P3∨(Km))∪G及(C3∨(Km))∪G的优美性

将k-优美图的概念进行了推广,引入A～B优美图的概念,并以此为基础,得到了非连通图(P3∨(Km))∪G及(C3∨(Km))∪G是优美图的一个充分条件.证明了对任意正整数k,m,n,t,当k≤n≤t,n+k-1≤m时,图(P3∨(Km))∪(k∪j=1Kn,t)和(C3∨(Km))∪(k∪j=1Kn,t)是优美图;当k=1,2,2≤n＜2m+1时,图(P3∨(Km))∪k∪j=1P(j)n,(C3∨(Km))∪k∪j=1P(j)n和(P3∨(Km))∪Pn∪St(t)是优美图;当2≤n≤2m +1时,(C3∨(Km))∪Pn∪St(t)是优美图.本文的结果推广了现有的一些结论.