两类特殊图的符号星控制数

针对“关于图的符号星控制数”一文中有一个定理(关于完全图的符号星控制数)的部分结果是不正确的,文章给出正确的结论及其证明,并确定了k-正则二部图的符号星控制数。     

两类特殊图的(2,1)-全标号

一个图G的(p,1)-全标号是一个映射f:V(G)∪E(G)→{0,1,…k},使得:G的任两个相邻的顶点得到不同的整数;G的任两个相邻的边得到不同的整数;一个点和它的邻边得到的整数至少相差p.(p,1)-全标号的跨度是指两个标号差的最大值.图G的(p,1)-全标号的最小跨度叫(p,1)-全标号数,记作λT,(G).本文得到了两类特殊图的(2,1)-全标号数.     

线图连通度的界

首先给出了线图连通度κ_L的一个上界;κ_L≤δ+△-2;其次得出了在条件δ≥[n/2]+1下κ_L的一个很好的下界;κ_L≥2δ-2;由此得到当δ≥[n/2]+1时,若G为正则图,则κ_L=2δ-2,若G为拟正则图,则κ_L=2δ-2或2δ-1。     

Halin图的均匀染色

Halin图是最小度不小于3的3－连通平面图,且存在一个面,删除关联于该面的所有边后是一棵树。称图G为均匀k-可着色的,如G的顶点集V可分划成K个独立集V1、V2、…Vk,使||Vi|-|Vj||≤1（0≤i＜j≤k）;称使图G的均匀k-可着色的最小整数k为G的均匀色数,记为xe（G）。本文对非K4的Halin图证明△（G）≠4时,对任意的整数k≥［△（G）／2]＋1;当△（G）＝4时,对任意整数的k≥4,G是均匀k-可着色的。从而对Halin图证明了均匀染色猜想（ECC）。     

图与其补图特征值之和的界

设G是n阶简单图,其补图记为Gc,iλ(G)为G的第i大特征值。文中给出了图与其补图几个常见的特征值之和的界(i=1,2,…,n):-2(nn--1 i)(+i-1 1)≤λi(G)+λi(Gc)≤2(n-i)i(n-1)()及n-1≤λ1(G)+λ1(Gc)≤-1+1+2n(n-1)()()式中,下界可达当且仅当G为正则图。     

积图P_2×C_6的邻点可区别全染色

设G是阶数不小于3的简单连通图,G的k-正常全染色σ称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同,这样的k中最小者称为是G的邻点可区别全色数．得到了P_2×C_6的邻点可区别全色数．     

完全二部图的拟C_(2k)-因子分解

λKm,n表示完全二部多重图,kC2表示2k长圈。如果λKm,n的子图F包含λKm,n的m+n-1个点,且其每个分支都同构于kC2,则称F为λKm,n的拟kC2-因子。如果λKm,n的边集可以划分为λKm,n的拟kC2-因子的和,则称λKm,n存在拟kC2-因子分解。本文利用直接构造法,得到完全二部多重图λKm,n存在拟kC2-因子分解的充分必要条件是:(1)λ=0(mod 2),(2)m=n+1,(3)n=0(mod k)。     

积图P2×C6的邻点可区别全染色

设G是阶数不小于3的简单连通图,G的k-正常全染色σ称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同,这样的k中最小者称为是G的邻点可区别全色数.得到了P2×C6的邻点可区别全色数.     

关于笛卡儿积1—因子分解的进一步结果

设G为无桥三次图,文[1]证明了G×K_3存在1-因子分解的充分条件。通过引入“圈图”概念,给出了G×K_3存在1-因子分解的判别法则。本文给出笛卡儿积1-因子分解的进一步结论和判则。 关于无桥三次图G和K_3的笛卡儿积G×K_3的1-因子分解,已有结论如次。 (Ⅰ)若G有一个同构于E×K_3的子图H(E表示单一的一条边),G_1是图G中H代之以H_1=P_(2k+1)×K_3得到的新图(P_(2k+1)表示长(2h+1)的路)。假定G的边被t种颜色如此着色:t≥5,H的侧面边的颜色取自{1,2,3,4}。则G_1的边能够这样着色:H_1的端面边和所有不在H_1中的边按G中着色,H_1侧面边和H_1内部三角形的边仅用颜色{1,2,3,4}着色。([1]引理2)。     

对一类最小图的研究

对一个与并行结构和通信网络设计密切相关的图论公开性问题进行了研究。讨论了图的结点数为n,连通度至少为k,k-直径至多为d的条件下的最小图问题,给出了一般条件下最小图边数条数的上、下界,在此基础上,得到了两种条件下最小图边数的计算公式,结合已有的图论结果,对文中所提到的最小图进行了构造。     

一类Halin-图的均匀色数

对Δ(G) =4的Halin -图证明了 |V(G) | 0 (mod3)时 ,对任意整数的k≥「Δ(G) / 2 +1,G是可均匀k -可着色的。从而证明了这类Halin -图的均匀染色数的下界是「Δ(G) / 2 +1。     

单圈图和双圈图的群色数

若图G=(V,E),给定方向为D,A表示一个非平凡的阿贝尔群,F(G,A)表示映射f:E(G)→A的集合。若对任意f∈F(G,A)存在映射c:V(G)→A,使得G中的每一条有向边e=uυ∈E(G)(方向是u→υ)满足c(u)-c(v)≠f(e),这时说图G是A-可染的。使得图G在方向D下是A-可染的,A的最小阶数为图G的群色数,记为χg(G)。在分析单圈图和双圈图特性的基础上,讨论了它们的群色数。对于单圈图、双圈图可得出其群色数都是3。     

连通图生成树的叶子数

图G的一度点称为G的叶子．证明了对G的生成树的叶子数最小值到G的生成树的叶子数的最大值之间的任何整数，G都有某个生成树的叶子数等于这个值．     

4度循环图的宽直径

研究了涉及图中两点间k条内部不交路的图的宽距离和宽直径。根据循环图的传递性和对称性,得到了n阶4度连通循环图的宽直径的上下限。所得结果可用来度量以循环图作为模型的一类具有高度对称性的网络的通信传输的延迟性能和容错性能。     

一类团横贯数等于团独立数的图

把图G的每一个团看作一个点，两点之间有边相连当且仅当它们对应的团有非空交（即有公共点）．这样得到的图称为图G的团图，记为K（G）．文章证明了如果一个图对应的团图为二部图，则该图的团横贯数等于团独立数，即τc（G）=ac（G），另外给出了判断一个图的团图是否为二部图的一个计算时间为o（n^4）的多项式时间算法．     

2类非连通图的优美性

本文利用构造法,研究了2类非连通图图m·C3∪Gm-1及m·(P2∨K2—)∪Gm-1的优美性.证明了下面的结论:设m为任意的正整数,Gm-1是表示边数为m-1的优美图,则当m≥2时,图m·C3∪Gm-1及m·(P2∨K2—)∪Gm-1都是优美图.其中,C3是表示三个顶点的回路图,P2∨K2—是两个顶点的路P2与两个孤立顶点的图K2—的联图,m·C3是m个图C3恰有一个公共点的图,m·(P2∨K2—)是m个图P2∨K2—恰有一个公共点的图,G∪Gm-1是把图G与Gm-1不相交并起来所得的非连通图.     

外平面图的边列表染色

如果一个平面图的顶点均位于一个面的边界上，则称此图为外平面图。图的边列表色数（边选择数）是满足下列条件的最小非负整数k，并记为X'L（G）：对G的每一条边e任意配一由k种颜色组成的色集（色表）L（e），G的每条边可以着从L（e）中选择出的一种颜色，使着色正常。本文对Δ（G）≠3的外平面图证明了列表染色猜想：X'L（G）＝X’（G）。     

k点可删的ID-因子临界图的度条件

研究了κ点可删的ID-因子临界图的度条件，得到使图G是κ点可删的ID-因子临界图的度的下界，同时说明该结果是严格的．     

强N_2-局部连通无爪图的Hamilton性

运用反证法的证明技巧,对任一无爪图G及其圈C,证明了只要C上有一个接触点是强N_2-局部连通的,则C一定不是最长圈.即证明了强N_2-局部连通无爪图是Hamilton图.