一类优美图的充要条件

对于一个简单图G=(V,E),若存在整数l(v)是G中顶点v的标号,当e=uv时,e的标号l’(e)=|l(u)-l(v)|,并且满足 (a)(?)u,v∈V(G),当u≠v时,l(u)≠l(v); (b)max{l(v)|v∈V(G)}=|E(G)|=ε; (c)(?)e′,e″∈E(G),当e′≠e″时,l′(e′)≠l′(e″)。则称G为优美图(graceful graph)。     

关于P_(2r,2s-1)的k-优美标号

对于简单图G=,如果存在一个映射f:V(G)→{0,1,2,…,|E|+k-1}满足:1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);2)max{f(u)|u∈V}=|E|+k-1;3)对任意的e1,e2∈E,若e1≠e2,则g(e1)≠g(e2),且{g(e1)|e∈E}={k,k+1,…,|E|+k-1},g(e2)=|f(u)-f(v)|,e=uv,则称G是k-优美图,f称为G的k-优美标号.作者研究了一类图的k-优美标号.     

直径为4的奇优美树

对于简单图G=, 如果存在一个映射f: V→{0,1,2,...,2E|-1}满足:对任意的u,v∈V,若u≠v,则f(u)≠f(v);max{f(v)|v∈V}=2|E|-1;对任意的e1,e2∈E,若e1≠e2,则g(e1)≠g(e2),此处g(e)=|f(u)-f(v)|,e=uv;{g(e)|e∈E}={1,3,5, ...,2|E|-1},则称G为奇优美图,f 称为G的奇优美标号.提出一个猜想:每棵树都是奇优美的,文章证明了直径为4的树都是奇优美的.     

图的corona积的局部反魔幻着色数

令G=(V(G),E(G))是具有n个顶点、m条边的连通简单图.称一个双射f:E(G)→{1,2,…,|E(G)|}为图G的一个局部反魔幻标号,如果f满足对于G中任意两个相邻的顶点u和v都有w(u)≠w(v),其中w(u)=∑e∈E(u)f(e),E(u)是与点u相关联的边的集合.若对图G的顶点v着颜色w(v),则图G...     

关于优美图Bodendiek猜想的一种推广

Bodendiek猜想一个圈加一条弦是优美图。已由[1][2]和[3]给出证明。本文以矩阵为工具,证明了该猜想的一种推广:连结两个顶点的三条独立路所成简单图,在一定条件下是优美的。§1 预备知识首先罗列出有关概念。假如对于简单图G(V,E),Vv∈V,赋予一个非负整数ψ(v),则称图G是标定的。     

轮形图和扇形图的优美性

设L为简单无向图G的一个顶点标号,若L满足:(1)L为G的顶点集V到{0,1,…,|E|}的一个单射;(2)由L(′e)=|L(u)-L(v)|(其中e=uv)决定的边标号L′是从G的边集E到{0,1,…,|E|}的一个双射,则L称为图G的优美标号.论文研究了轮形图和扇形图的优美性,并给出它们的优美标号.     

几类特殊图的一般指标集

令G=(V(G),E(G))为一简单连通图,V(G)和E(G)分别是图G的顶点集和边集.一个顶点标号函数f:V(G)→Z2诱导出一个边标号函数f*:E(G)→Z2,其中?v1 v2∈E(G),有f*(v1v2)=f(v1)+f(v2).当标1和标0的顶点数相差m(m<|V(G)|)时,标号为1和0的边数差的集合称为图G...     

一类字典积Cn[H]的星全染色

简单图G和H的字典积G[H]是指具有顶点集V(G)×V(H)的简单图G[H],其顶点(u,v)和另一个顶点(u’,v’)相邻当且仅当uu’∈E(G),或者u=u’且vv’∈E(H).研究了n阶圈Cn与m阶简单图H的字典积Cn[H]的星全染色,得到了圈与某些特殊图的字典积的星全色数.     

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

设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*的奇优美标号,并给出了相应的标号算法及相关的一些证明.     

Ore-2型图中存在两个边不相重的Hamilton圈

本文讨论的图都是无向的简单图。设G是一个图,分别用V(G)和E(G)表示图G的顶点集和边集。又设u、v∈V(G),用d(v)或de(v)表示v的次数,用vu表示联结v、u的边。设G是一个图,|V(G)|=P,k是一个整数。若对任意{u、v}∈V(G)、uvE(G),有d(u) d(v)≥p k,则称图G是Ore—k型的[1]。     

C_n∨mC_n是反魔幻图

图G=(V,E)的标号是一个双射?:E→{1,2,3,…,|E|}.G的任一顶点u,其标号和f_?(u)=∑_(e∈E(u))?(e),这里E(u)是与顶点u关联的所有边的集合.1990年Hartsfield和Ringel提出了反魔幻图的概念.如果存在G的一个标号?,使得任意两个不同的顶点u,v有不同的标号和,即f?(u)≠f?(v).证明了联图C_n∨mC_n是反魔幻图.     

完全多部图的符号罗马控制数

设图G=(V,E)是一个简单无向图,若实值函数f:V→{-1,1,2}满足以下两个条件:(i)对于任意v∈V,均有∑_(u∈N[v])f(u)≥1成立;(ii)任意v∈V,若f(v)=-1,则存在一个与v相邻的顶点u∈V,满足f(u)=2,则称该函数为图G的符号罗马控制函数.定义图的符号罗马控制数为γSR(G)=min{f(V)f是图G的符号罗马控制函数}.通过对完全多部图中的顶点数进行分类,给出了当k≥3时,完全多部图K(n_1,…,n_i,…,n_k)的符号罗马控制数的准确值.     

结合图的导出匹配可扩性

简单图G和H的结合图G[H]的顶点集为V(G)×V(H),其中(u,v)和(u′,v′)相邻的充分必要条件是:或者uu′∈E(G)或者u＝u′并且vv′∈E(H).研究了结合图G[H]的导出匹配可扩性,证明了若G和H是非平凡图,G是连通图,且G和H满足下列条件之一,则G[H]是导出匹配可扩的:(1) G和H中有一个是导出匹配可扩的;(2) G和H都有完美匹配;(3) G和H中一个有完美匹配,另一个有几乎完美匹配.     

一类二部图的奇优美性

设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*的奇优美标号.     

Cartesian积图的最大拉普拉斯特征值

设G=(V(G)),E(G)),H=(V(H),E(H))是两个简单的连通图,定义与的Cartesian积G×H图是:其顶点集为V(G×H)=V(G)×V(H),其中任何两个顶点(u,u’),(v,v’),相邻当且仅当u=v且u’,v’在H中相邻;或u’=v’且u,v在G中相邻,这里u,v∈V(G),u’,v’∈V(H).本文研究两个图的Cartesian图的拉普拉斯矩阵的最大特征值,得到如下结论:设简单图G具有n顶点m条边,图H具有P个顶点q条边,那么G和H的Cartesian积图G×H的拉普拉斯最大特征值p(L(G×H))≤2m/n[1+(n-1)(((n3/4m2)-(1/n-1))～(1/2))]+((2p-1)～(1/2))+1.     

拟Mobius梯子的L(1,1,1)-标号

图G的一个L(1,1,1)-标号是从顶点集V(G)到非负整数集的一个映射f,且当距离d(u,v)=1,2,3时,均有|f(u)-f(v)|≥1;其中,u,v是图G的顶点.不妨设0为最小标号,则称图G的所有L(1,1,1)-标号中的最大跨度的f(v)最小数为图G的L(1,1,1)-标号数,记为λ_(1,1,1)(G).给出了拟Mobius梯子的L(1,1,1)-标号数的确切值或上下界.     

合成图C_n[H]的星全染色

简单图G和H的合成图是指具有顶点集V(G)×V(H)的简单图G[H],它的顶点(u,v)和另一个顶点(u′,v′)相邻当且仅当或者uu′∈E(G),或者u=u′且vv′∈E(H).论文研究了n阶简单图G与m阶简单图H的合成图的星全染色,其中G为n阶圈,得到了圈与某些特殊图的合成图的星全色数.     

关于Haj■s猜想

Hajs猜想:每顶次数皆偶的图G可表示成不多于[v/2]个边不相交的圈的并,其中v是G的顶数。本文对于平面图证明Hajs猜想。以下记G=(V,E),V是顶集,E是边集,v=|V|为顶数,ε=|E|为边数,次数d(u)为偶数(奇数)的顶u称为偶顶(奇顶)。     

关于链路P_n(m_1,m_2,…,m_(n-2))的k-优美性

图G的标号是指G的顶点集到一个整数集的映射g,且对e=uv∈E(G)由g(u)和g(v)诱导出边e的标号.本文给出了链路P_n(m_1,m_2,…,m_(n-2))的k-优美标号.即证明了图P_n(m_1,m_2,…,m_(n-2))是k-优美图.进而推广了原有的一些结果.     

一类单圈图的优美性和平衡性

设L为简单无向图G的一个顶点标号,L称为图G的优美标号,若L满足以下两条：（1）L为G的顶点集V到{0,1,2,…,｜EI｜}的一个单射;（2）由L’（e）=｜L（u）-L（v）｜（其中e=uv）决定的边标号L’是G的边集E到{1,2,…,｜EI｜}的一个双射．进一步,若存在正整数c,使得对每一个uv ∈ E（G）满足L（u）≤c〈L（v）或L（w）≤c〈L（u）,则称L为图G的平衡标号,其中c为平衡特征．主要研究一类单圈图的平衡性并给出相应的平衡标号及其特征．