图的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...     

边染色图中的2-因子

令G是含n个点的边染色图,对G中任意顶点x,定义其色邻域CN(x)为集合{c(xy)|xy∈E(G),y∈V(G)}。如果G中任意相邻的两条边都染有不同的颜色,就称G是正常染色的。证明了如果边染色图G满足对V(G)中任意两点u,v有|CN(u)∪CN(v)|≥4n/3+8,则图G含有一个正常染色2-因子。     

变换图G++-的连通度

本文所研究的图G的变换图G++-是以V(G)∪E(G)作为顶点集的图,它的两个顶点u与v被一条边连接当且仅当下列情形之一成立:(ⅰ)如果u,v∈V(G),那么它们在G中邻接.(ⅱ)如果u,v∈E(G),那么它们在G中邻接.(ⅲ)如果u与v一个属于V(G)而另一个属于E(G),那么它们在G中不关联.文章给出了变换图G++-的连通度的一个下限.     

随机图的f-染色的分类

随机图G(n,p)是具有n个标号的顶点的图,并且图中的每一顶点对都以概率p被随机且独立地选择为图G的边。特别地,当■时,得到一个概率空间,其中n个顶点上的所有标号图是等概率的。对于有顶点集V和边集E的简单图G=(V,E),G的f-染色c是广义的边染色,使每个颜色类在任一顶点v上至多出现f(v)次,其中f(v)是分配给v的正整数。给出随机图■是f-第一类的一个充分条件。     

几类特殊图的一般指标集

令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...     

无三角形3-正则图的几个参数的界

图G的一条边称为割边是指删去该边后,使得余下的图的连通分支数增加。图G 中的一个两两不相邻的边子集称为图G 的一个匹配。图G 的一个最大匹配的边数称为图G 的匹配数。图G 中的一个与G 的每个团都有交的顶点子集称为G 的一个团横贯集,图G 中元素个数最少的团横贯集的顶点数称为G 的团横贯数。本文针对n阶连通无三角形的3-正则图G=(V(G),E(G)),首先给出了其割边数的一个上界(n-10)/4;其次对它的匹配数得到了一个下界(11n-2)/24;再次对它的线图的团横贯数呈现了一个上界(13|E(G)|+3)/36。同时刻画了达到这些界的极值图。
     

图的关于边删除的外连通控制

对于图G=(V,E),如果V\S中的每个顶点都和S中至少1个顶点相邻,且G[V\S]是连通的,则称V的子集S是图G的外连通控制集.外连通控制集的最小基数~γc(G)称为图G的外连通控制数.给出了树删去1条边后对应的外连通控制数的可达下界,定义了关于边删除的~γc-严格图及~γc-稳定图,并对其相关性质进行了讨论.     

禁用两个子图的图的全控制数

设G=V(V,E)是一个简单无向图.一个点悬挂三个一度点的图称为爪图,D图是一个三角形其中两个点各悬挂一条长为2的路.如果图G的任何导出子图都不同构于爪图也不同构于D图,则称G为无爪和无D图.设S是V的非空子集,如果不在S的点一定与S中的某个点相邻,则称S为G的控制集.如果G中的点一定与S中的某个点相邻,则S称为G的全控制集.最小全控制集包含顶点的数目称为全控制数.给出了当G是N阶连通的无爪和无D图时全控制数紧的上界.     

折叠交叉立方体的限制连通度

限制性连通度作为评估互联网络容错性的最佳参数之一,在多处理器系统中对可靠性计算起着重要作用.给定一个连通图G=(V,E)和一个非负整数h,子集F?V(G)(F?E(G))(如果存在)称为h-限制点割(h-限制边割),如果G-F不连通,并且G-F中的每个连通分支至少有h+1个顶点,其中最小的h-限制点割(h-限制边割)的基数称为图G的h-限制连通度(h-限制边连通度),记为κh(G)(λh(G)).本文确定了h=2时n-维折叠交叉立方体FCQn的κh(G)和λh(G).     

优美图Bodendiek猜想的一种推广

Bodendiek 猜想一个圈加一条弦是优美图.已由[1][2]和[3]给出证明.本文以矩阵为工具,证明了该猜想的一种推广:连结两个顶点的三条独立路所成简单图,在一定条件下是优美的.假如对于简单图 G(V,E)的u∈V,赋以一个非负整数(v),则称图 G 是标定的,(v)称为顶点 v 的标号,|(u)—(v)|称为棱 uv 的标数.定义:若图 G(V,E)有满足下列条件的标号,则称 G 是优美图(graceful graph):     

圈与路联图点可区别Ⅰ-全染色和点可区别Ⅵ-全染色

一个图G的Ⅰ-全染色是指若干种颜色对图G的全体顶点及边的一个分配使得任意两个相邻点及任意两条相邻边被分配到不同颜色.图G的Ⅵ-全染色是指若干种颜色对图G的全体顶点及边的一个分配使得任意两条相邻边被分配到不同颜色.对图G的一个Ⅰ(Ⅵ)-全染色及图G的任意一个顶点x,用C(x)表示顶点x的颜色及x的关联边的颜色构成的集合(非多重集).如果f是图G的使用k种颜色的一个Ⅰ(Ⅵ)-全染色,并且u,v∈V(G),u≠v,有C(u)≠C(v),则称f为图G的k-点可区别Ⅰ(Ⅵ)-全染色,或k-VDITC(VDVITC).图G的点可区别Ⅰ(Ⅵ)-全染色所需最少颜色数目,称为图G的点可区别Ⅰ(Ⅵ)-全色数.利用组合分析法及构造具体染色的方法,讨论了圈与路的联图C_m∨P_n的点可区别Ⅰ(Ⅵ)-全染色问题,确定了这类图的点可区别Ⅰ(Ⅵ)-全色数,同时说明了VDITC猜想和VDVITC猜想对于这类图是成立的.     

图中顶点子集的边连通度与最优分级边连通图的构造问题

G =(V ,E)是无向连通图 ,无环允许有重边 .S是V的至少包含两个顶点的子集 ,S的边连通度λG(S)被定义为使S中的顶点不属于同一连通分支所需去掉的最少边数 .给定集合V和V的一个划分V =V1∪V2 ∪…∪Vr(|r|≥ 1,|V1|≥ 2 )以及正整数序列k1>k2 >… >kr≥ 2 .记Si=V1∪V2 ∪…∪Vi,1≤i≤r.构造一个连通图G =(V ,E)满足 :λG(Si)≥ki(1≤i≤r)且边数 |E|最小 .这种图G称为与所给划分和正整数序列相对应的最优分级边连通图 .在给出顶点子集的边连通度概念的基础上 ,本文提出并讨论了有关最优分级边连通图的构造问题     

关于二连通图中的最长圈

§1 符号及预备知识本文中提到的图论中最基本的概念,例如点、边、链、圈、子图、主子图等,均按一般图论书中的定义。文中的链(圈)指的是初等链(圈),图指的是简单图。图G的点集记作V(G),边集记作E(G),G中包含的最长圈的长度称为G的周长,记为c(G)。设(?)V(G),(?)V(G),(?)∩(?)=φ,Y是一条起点属于(?)而终点属于(?)的链,且V(Y)中别的点均不属于(?)∪(?),则称Y是一条(?)-(?)链,特别,当链长为1时,称为一条(?)-(?)边。若(?)={A},(?)={B},称Y为A-B链。设u∈V(G)。u在G中的邻域指的是这样的点集{u∈V(G)|uu∈E(G)},记作N(u)。如果Y是G的子图,我们将V(Y)导出的子图记为G(Y)。     

图的特征根

设G=(V(G),E(G)) 是顶点集为V(G)边集为E(G)的简单图. 用A(G)表示图G的邻接矩阵.A(G)的特征根称为图 G的特征根.主要研究图Ksn-s的邻接谱.     

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.     

若干图的倍图的邻点可区别边(全)染色

设G是具有顶点集V(G)和边集E(G)的简单图。如果G的一正常边染色σ满足对任意uv∈E(G),有Cσ(u)≠Cσ(v),其中Cσ(u)为点u的关联边所染颜色构成的集合,则称σ为G的邻点可区别边染色。如果G的一正常全染色σ满足对任意uv∈E(G),有Sσ(u)≠Sσ(v),其中Sσ(u)表示点u及u的关联边所染颜色构成的集合,则称σ为G的邻点可区别全染色。图G的邻点可区别边(或全)染色所需的最少的颜色数,称为G的邻点可区别边(或全)色数,并记为χ’as(G)(或χat(G))。给出了图G的倍图D(G)的以上两个参数的上界,并对完全图与树,确定了它们的倍图的邻点可区别边色数与全色数的精确值。     

近完全图的点可区别Ⅰ-全染色及Ⅵ-全染色

图G的一个一般全染色是指使用若干颜色对图G的全部顶点及边的一个分配,如果任意两个相邻点和两条相邻边染以不同颜色,则称为图G的Ⅰ-全染色;如果任意两条相邻边染以不同的颜色,则称为图G的Ⅵ-全染色。图G的一个Ⅰ-全染色(或Ⅵ-全染色)f,若对?u,v∈V(G),u≠v,都有C(u)≠C(v),其中C(x)表示在f下点x的颜色以及与x关联的边的色所构成的集合,则f称为图G的点可区别的Ⅰ-全染色(或点可区别Ⅵ-全染色),简称为VDIT染色(或VDVIT染色)。令χ■(G)=min{k|G存在k-VDIT染色},称χ■(G)为图G的点可区别Ⅰ-全色数。令χ■(G)=min{k|G存在k-VDVIT染色},称χ■(G)为图G的点可区别Ⅵ-全色数。利用分析法和反证法,讨论并给出了近完全图的点可区别Ⅰ-全色数和Ⅵ-全色数。     

树的D(r)-点可区别边染色

图G的一个正常边染色是指对G的每条边分配一种颜色使得任意相邻的两条边的颜色不同.图G的正常边染色f称为D(r)-点可区别边染色,如果对G中任意两个距离不超过r的顶点u,v∈V(G),有C'(u)≠C'(v),其中C'(x)={f(xy):xy∈E(G)}.图G的D(r)-点可区别边色数是指对图G进行D(r)-点可区别边染色所需要的最小色数,记为'r(G).文章讨论了树的D(2)-点可区别边染色及D(3)-点可区别边染色问题,通过逐层染色的方法,得到了树的D(2)-和D(3)-点可区别边色数的上界,并给出了线性时间的染色算法.另外,通过边染色与全染色的关系,得到了树T的D(3)-点可区别全色数不超过Δ(T)+3,D(2)-点可区别全色数不超过Δ(T)+2.     

图的点可区别无圈边色数的一个上界(英文)

图G的一个正常边染色f,若满足:1)G中无2-色圈;2)对于V(G)中的任意两点u和v,有C(u)≠C(v),这里C(u)={f(uw)|uw∈E(G)},则f叫做图G的一个点可区别无圈边染色.图G的点可区别无圈边色数,记为χ′_(vda)(G),是图G的一个点可区别无圈边染色所用色的最小数目.证明了若图G是一个最小度不小于5,且顶点数不超过30Δ~4的图时,χ′_(vda)(G)≤10Δ~2,其中Δ是图G的最大度.     

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是反魔幻图.