偶圈冠图r-C_n的奇优美性及奇优美性算法

图G的一个奇优美标号是指存在一个双射函数L:V(G)→{0,1,2,…,2|E|-1}使得任意边e=uv∈E(G),由L′(e)=|L(u)-L(v)|决定的边标号L′为E(G)到{1,3,…,2|E|-1}的双射。根据奇优美图的定义,文章讨论了偶圈冠图r-Cn的奇优美标号问题,证明了当n≡0(mod 4)时,偶圈冠图r-Cn是奇优美图,给出的新奇优美标号算法不同于现有的文献结果。     

偶圈的Turán数和Wenger图

设G是一个图,G的Tur(a)n数记作ex(n;G),是指阶数为n的不含G作为子图的图的最大边数.根据Erd(o)s在1965年给出的偶圈C2m的Tur(a)n数ex(n;C2m)的上界10mn1+1/m和Wenger在1991年构造的偶图Hm(q),并由这种图得到的ex(n;C2m)(m=2,3,5)的下界cn1+1/m(其中c为一个与n无关的常数),可以知道,当n→+∞时,ex(n;C2m)=O(n1+1/m)(m=2,3,5).n1+1/m就是ex(n;C2m)的准确阶.给出了Wenger图Hm(q)的一些一般性质,并分别构造了Hm(q)中长为8的圈(m≥4)和Hm(q)中长为12的圈(m≥6), 从而证明了不可能由图Hm(q)得到ex(n;C2m)的所有准确阶.     

一类二部图的奇优美性

设L为简单无向图G的一个顶点标号,L称为图G的奇优美标号,若L满足:1)L为G的顶点集V到{0,1,…,2|E|-1}的一个单射;2)由L'(e)=|L(u)-L(v)|(其中e=uv)决定的边标号L'是从G的边集E到{1,3,…,2|E|-1}的一个双射.根据奇优美图的定义,研究了一类二部图G*的奇优美标号.     

自同构群的阶为2pq2的一类群

给出了自同构群的阶为2pq2的一类群的分类,其中p和q是任意不同的奇素数,且q大于3.得到的主要结果是:若G不为无非平凡交换直因子的非幂零群,且|Aut(G)|=2pq2(p,q是奇素数,p≠q,q>3),则G同构于C(2p+1)3,C2pq2+1,C2×C(2p+1)3,C2×C2pq2+1之一.     

无爪图中具有指定长度的路因子

在无爪图G中,设σ2(G)表示不相邻顶点度和的最小值. 令|V(G)|=n=∑ki=1ai,ai6,1ik,并且σ2(G)n+k-1,证明了对于图G中任意的k个顶点v1,v2,…vk, 都存在点不相交的路P1,P2,…Pk，使得对于1ik，都有|V(Pi)|=ai并且vi是路Pi的一个端点.     

关于图运算的和连通指标（英文）

设G=(V,E)是一个简单的连通图,V(G)和E(G)分别是图G的顶点集和边集,其中|V(G)|=n,|E(G)|=m.设d_i是点v_i的度数,i=1,2,…,n.Zhou和Trinajasti c′定义了一个新的拓扑指标,命名为和连通指标,记作X(G)并定义为X(G)=∑uv∈E(G)1/(d_u+d_v)~(1/2).该文得到了包括图的交,并,科罗纳积,笛卡尔积,和对称差的图运算的和连通指标.     

冠的拉普拉斯谱

主要研究冠的拉普拉斯谱.设G1 G2是两个简单连通图G1和G2的冠,L1是G1的拉普拉斯矩阵,μ1,μ2,…,μm是G2的拉普拉斯谱,且0=μ1<μ2≤…≤μm,利用分块矩阵证明了G1 G2的拉普拉斯矩阵L的特征多项式|λI-L|=[Πmi=2(λ-1-μi)n]-L1-(λ-m-1)IλI(λ-1)I,其中|V(G1)|=n,|V(G2)|=m.     

轮W_(2n 1)=C_(2n)☉K_1的调和标号

设G=(V(G),E(G))是一个连通的无向的简单图,图G的调和标号,即给出一个映射h:V(G)→{0,1,2,…,q} 由它导出的边的标号 h(a,b)=h(a) h(b),(mod q,对任意(a,b))是|—|的。本文给出了轮Cn⊙K_1当n是偶数时的调和标号。     

一类串图的1-维魔幻标号

如果有整数对(s_i,t_i)(i∈[1,m])和一一映f:V(G)∪E(G)→[1,p+q],对每一条边uv∈E(G),使得f(u)+f(v)=s_i+t_if(uv),则称f是图G的(s_i,t_i)~m_i=1-魔幻标号。进一步,若存在最小的正整数k,使得G的任何一个(s_i,t_i)~m_i=1-魔幻标号满足m≥k,则称G为k-维(s,t)-魔幻图。为此,定义了图G的魔幻全空间与向量空间,并用向量代数方法研究串图G,得到图G有1-维(s,t)-魔幻全标号。给出了1-维(s,t)-魔幻全标号与奇优美标号、对偶标号之间的关系,及用具有1-维-魔幻全标号的二部分(p,q)-图G来构造大规模的1-维-魔幻全标号图的方法。     

偶圈的Turán数和Wenger图

设G是一个图,G的Turán数记作ex(n;G),是指阶数为n的不含G作为子图的图的最大边数.根据Erds在1965年给出的偶圈C2m的Turán数ex(n;C2m)的上界10mn1 1/m和Wenger在1991年构造的偶图Hm(q),并由这种图得到的ex(n;C2m)(m=2,3,5)的下界cn1 1/m(其中c为一个与n无关的常数),可以知道,当n→ ∞时,ex(n;C2m)=O(n1 1/m)(m=2,3,5).n1 1/m就是ex(n;C2m)的准确阶.给出了Wenger图Hm(q)的一些一般性质,并分别构造了Hm(q)中长为8的圈(m≥4)和Hm(q)中长为12的圈(m≥6),从而证明了不可能由图Hm(q)得到ex(n;C2m)的所有准确阶.     

广义太阳图S_(m,n)奇优雅标号算法及实现

给出了广义太阳图S_(m,n)的定义,设计了该类图的奇优雅标号算法,证明了算法的正确性和广义太阳图S_(m,n)的奇优雅性。利用Matlab语言编制了"广义太阳图S_(m,n)奇优雅标号算法"程序并通过实验数据说明算法的有效性。     

关于图的L(3,2,1)-标号问题

图G的L(2，1)-标号是一个从顶点集V(G)到非负整数集的函数f(x)，使得若d(x，y)=1，则|f(x)-f(y)|≥2；若d(x，y)=2，则|f(x)-f(y)≥1．图G的L(2，1)-标号数A(G)是使得G有max{f(v)：v∈V(G)|=k的L(2，1)-标号中的最小数k．将L(2，1)-标号问题推广到更一般的情形即L(3，2，1)-标号问题，并得出了全图、块图的L(3，2，1)-标号数的上界．     

完全三部图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)是色唯一图。     

几种正规积图的带宽

引言设G是个图,V(G)是G的顶点集,E(G)是G的边集。|V(G)|=n,如所周知,任一个1—1对应的函数f:V(G)→{1,…,n}均称为V(G)(或G)上的一个标号。规定f的带宽为B(f)=max{|f(u)-f(V)|:uv∈E(G)},而图G的带宽的定义则是B(G):min{B(f):f是G上的标号}。例如,图1即给出了一个很简单的图G_0的两种不同的标号:     

S(3,n)的k-边优美的图标号

设k为非负整数,G是一个p点q边图,如果将G的边用k,k+1,k+2,…,k+q-1进行标号,而顶点标号模p运算后各不相同,则称G是k-边优美的.对于所有满足G为k-边优美图的非负整数k所构成的集合称为图G的边优美指标集.该文给出了图G=(V,E)为k-边优美的定义,根据轮图的特殊性质,讨论了S(3,n)为k-边优美图的必要条件.根据所得的必要条件,利用递归的方法构造S(3,n)的k-边优美图标号并给出详细证明,从而完全解决了当n为偶数时S(3,n)的边优美指标集问题.     

一类新图的奇优美性的研究

设L为简单无向图G的一个顶点标号,L称为图G的奇优美标号,若L满足以下两条:(1)L为G的顶点集V到{0,1,…,2 ︱E︱-1}的一个单射;(2)由L′(e)=︳L(u)-L(v)︳(其中e=uv)决定的边标号L′是从G的边集E到{1,3,…,2 ︱E︱-1}的一个双射.本文给出了一类特殊简单图G*的奇优美标号,并给出了相应的标号算法及相关的一些证明.     

图的L(p,q)-标号问题

令G为图,p,q为2个正整数,p≥q。G的一个L(p,q)-标号是映射f:V(G)→{0,1,2,…},使得对任意x,y∈V(G),若dG(x,y)=1则|f(x)-f(y)|≥p;若dG(x,y)=2则|f(x)-f(y)|≥q。G的一个m-L(p,q)-标号是标号f:V(G)→{0,1,2,…},使得对任意x∈V(G),有f(x)≤m。并称λp,q(G)=min{m|存在G的一个m-L(p,q)-标号}为图G的L(p,q)-数。本文给出k-退化图、G1和G2的联图G1∨G2及G1和G2的M-matched sum图G1M G2的L(p,q)-数不同上界。最后给出仙人掌图,唯一圈图L(p,1)-数λp,1(G)的可达界。     

两类并图的优美标号

讨论2n个优美二分图与一条通路并的优美性,得到如下结论:设二分图G=(X,Y,E)优美,优美标号为θ,边数为q,a=max{k|0相似文献   

在大的邻域并图中长的控制路

设G是一个图。令 NC(G)=min{|N(u)∪N(V)|{u,v)(?)V(G),uv(?)E(G)},本文主要结论如下:定理1 设 G 是3—连通图,|V(G)|=n,{a,b)(?)V(G).若 G 含有一条(a,b)—控制路,则 G 中存在(a,b)—控制路 P,使得|V(P)|≥min{n,2NC(G)-1}定理2 设 G 是3—连通图,|V(G)|=n,NC(G)≥1/2(n+1).若对于任意{a,b)(?)V(G),G 中都有(a.b)—控制路,则 G 是 Hamilton—连通的。     

笛卡尔图的无圈边染色

研究图的结构时会发现,很多结构相对复染的图基本上是由一些结构简单的图通过笛卡尔积运算得到的,所以,可以根据笛卡尔积图的结构特征把两个简单图和进行笛卡尔积运算,其中|V(G)|=n,|V(H)|=m,可以把笛卡尔积图G×H分解成为m个不相交的G的拷贝和n个不相交的H的拷贝,用图分解法和染色构造法研究一些笛卡尔积图的无圈边染色包括路与圈、轮、扇的笛卡尔积图无圈边染色数.