单圈图的D(2)-点和可区别全染色

图G的D(2)-点和可区别全染色是指在图G的一个正常全染色φ下,G中任意两个距离不超过2的顶点u,v,其色集合中所有颜色数之和互不相同.使得G有一个k-D(2)-点和可区别全染色的最小整数k,称为图G的D(2)-点和可区别全色数.文中应用组合零点定理和权转移方法刻画了单圈图的D(2)-点和可区别全染色,并得到其D(2)-点和可区别全色数.

一类仙人掌图的D(2)-点可区别全染色

用数学归纳法和组合分析法给出最大度为3的仙人掌图G T的D(2)-点可区别全染色,进而得到χ_(2vt)(G T)≤6.结果表明,D(β)-VDTC猜想对最大度为3的仙人掌图成立.

三类联图的2-距离和可区别边染色

该文探讨了C_(m)·P_(n)、C_(m)·S_(n)和C_(m)·K_(n)三类联图的2-距离和可区别边染色问题.根据联图的结构特点,利用组合分析法、反证法以及分类讨论思想,得到了这三类联图的2-距离和可区别边色数.结论表明三类联图的2-距离和可区别边色数均不超过Δ+2.

一些特殊图的中间图的2-距离和可区别全染色

为了进一步研究图的2-距离和可区别全染色问题,根据中间图的构造特点,通过构造染色函数,利用组合分析法得到了路,圈,星,扇,轮,双星以及轮环图的中间图的2-距离和可区别全色数.

笛卡儿积图的2-hued列表染色

给定图G的一个列表分配L,图G的一个(L,r)-染色,是一个正常染色c满足:每个顶点v都至少和min{d(v),r}种不同颜色的顶点相邻,并且c(v)属于L(v).图G的r-hued列表染色数,记为χL,r(G),是最小正整数k满足对于任意一个|L(v)|=k的列表分配L,图G有一个(L,r)-染色.最后证明了χL,2(P_(m)□P_(n))=4,并且确定了χL,2(P_(m)□C_(n))的范围.

容许对称群的有限2-弧传递图

如果图Γ至少有一个2-弧且其自同构群在点集和2-弧集合上是传递的,则称该图为2-弧传递图.设G是基柱为交错群Ac(其中c≥5)的几乎单群,利用陪集图概念构造无平方因子阶的(G,2)-弧传递图.再通过分析自同构群和其点稳定子群的子群链结构,给出了该类图的分类.

不含短圈平面图的2-距离列表染色

图的染色理论在图论中有着重要的地位.主要运用权转移技巧,通过结构分析,研究了不含4-圈和5-圈的平面图的2-距离列表染色.降低了这类平面图的2-距离(Δ+4)-列表染色的最大度下界,证明了不含4-圈和5-圈且Δ≥12的平面图是2-距离(Δ+4)-列表可染的.

无三角形IC-可平面图的线性2-荫度

设G为最大度为Δ的IC-可平面图。图G的线性2-荫度la_(2)(G)是将G分解为k个边不交森林的最小正整数k,其中森林的每个分支均为长至多为2的路。本文通过权转移方法研究了无三角形IC-可平面图的线性2-荫度,得到la_(2)(G)≤[△+1/2]+5。

双圈图的D(2)-点可区别边染色

图G的一个正常k-边染色f满足对■u,v∈V(G),当d(u,v)≤2时都有S_(f)(u)≠S_(f)(v),其中S_(f)(v)={f(vw)|vw∈E(G)}表示顶点v的所有关联边上所染颜色构成的集合,则称f为图G的k-D(2)-点可区别边染色(简记为k-D(2)-VDEC),将其所需要颜色的最小数k称为D(2)-点可区别边色数,简记为χ’_(2-vd)(G).结合Hall定理证明了最大度为△(G)的双圈图G都有χ’_(2-vd)(G)≤△(G)+2.

平方图的2-距离和可区别边染色

为了进一步研究图的2-距离和可区别边染色的问题.利用组合分析法、反证法以及分类讨论的思想,得到了路、圈、C_(n)∧P_(m)、C_(m)∧C_(n)、C_(n)∧P_(m)∧C_(k)等5类平方图的2-距离和可区别边色数,结果表明这5类平方图的2-距离和可区别边色数均不超过Δ+2.

若干倍图的2-距离和可区别全染色

为了研究图的2-距离和可区别全染色问题,根据倍图的结构特点,通过组合分析法和构造染色函数法,得到了路、圈、星、扇、轮、完全二部图的倍图的2-距离和可区别全色数.

禁用{B_(k+1),K_(2,l+1)}的图α谱半径极值问题

令K_(s,t)是完全二部图,K_(n)是完全图,其中s,t和n是正整数.令B_(4,l)是由l个共享一条边的K_(4)构成的图,B_(l)是由B_(4,l)的所有生成子图构成的集合.本文研究了禁用{B_(k+1),K_(2,l+1)}的图的最大α-谱半径问题.利用B_(k+1)和K_(2,l+1)的结构特点以及基本不等式,在具有n个顶点、最大度为Δ且禁用{B_(k+1),K_(2,l+1)}的连通图中,获得了α-谱半径的上界,且刻画了达到上界的极值图.相应地,在具有n个顶点、最大度为Δ且禁用B_(k+1)或K_(2,l+1)的连通图中,得到了α-谱半径的上界.

2-连通2-支配集的集中式构造

在无线传感器网络中,通常采用连通支配集来构成一个虚拟骨干网进行分层路由,对重要的目标或环境需要构造容错性高,可靠性好的虚拟骨干网。提出构造网络2-连通2-支配集的两种集中式算法,分别是先回路后支配和先支配后回路。前一种算法是先形成一个由支配点组成的回路,然后以此回路为基础不断地扩充此回路,直到不在回路中的节点为2-被支配为止;后一种算法是首先保证每个非支配点都要变成2-被支配点,然后再使图中所有支配点构成回路。

关于(g,f)-2-覆盖图和(g,f)-2-消去图

设G是一个图,用V(G)和E(G)表示它的顶点集和边集,并设g和f是定义在V(G)上的两个 整数值函数且g<f．图G的一个(g,f)-因子是G的一个支撑子图F使对任意的x∈V(G)有g(x)≤ dF(x)≤f(x)．如果过图G的任何两条边都有一个(g,f)-因子,则称图G是一个(g,f)-2-覆盖图．如果 图G的任何两条边不属于它的一个(g,f)-因子,则称图G是一个(g,f)-2-消去图．分别给出了一个图 是(g,f)-2-覆盖图和(g,f)-2-消去图的一个充分条件．

至多有2个等长圈的简单图的最大边数

设Sn是具有n个顶点至多有2个等长圈的简单图的集合。若Sn中不存在图G’使|E(C’)|>|E(G)|,Ng称G是简单的最大图分布(2)图(简记为简单MCD(2)图)。用f~*(n,2)表示具有n个顶点的简单MCD(2)图的边数。作者证明了f~*(n,2)≥(n-l)+[1/2(11n-20)^(1/2)]且当3≤n≤10时等式成立。

C_（60k^2）π－能谱的群论解析计算

本文推导出正二十面体（Ｉ＿ｈ）对称的同系碳簇Ｃ＿（６０ｋ￣２）π－轨道的群约化通式；在紧束缚（Ｈｕｃｋｅｌ）方案下，应用Ｌａｎｃｚｏｓ三对用比方法，对每一类不可约表示仅需造出一个基函数作为起始态，便可使６０ｋ￣２×６０ｋ￣２久期方程达到理想的方块化，系统地求出了Ｃ＿（６０）—Ｃ＿（２１６０）（ｋ＝１—６）按不可约表示分类的方块本证多项式和能级的解析形式（但五次以上代数方程只能求数值报）。文中叙述本方法的梗概，示范Ｃ＿（６０），Ｃ＿（２４０）及Ｃ＿（５４０）的计算结果。

一类(n,n+2)-图关于两种拓扑指标的排序

Hosoya指标和Merrifield-Simmons指标是化学图论中2个重要的拓扑指标。研究了一类(n,n+2)-图Tk的Hosoya指标和Merrifield-Simmons指标,根据Cm上2个接点u和v之间的距离,给出了该类图关于这两种拓扑指标的排序。

线图中2-因子分支数一些结果的改进

设G为一简单图,该文重点研究了图及其补图的线图中2-因子的分支数,改进了Nebesk■的一个结果,得出如下结论:阶数n≥5的简单图G,G和L(G)分别是G的补图和线图,存在一个图G′∈{G,■},线图L(G′)包含k个分支的2-因子,其中k=1,…,└(n-3)/4」.讨论了图及其补图的线图中2-因子分支的最大个数的界的问题,并给出了线图中存在一定分支数的2-因子的Chvtáal-Erds型条件,即对于阶为n的图G,如果k(G)≥a(G)-1,则L(G)中存在所有k个分支的2-因子,其中1≤k≤└n^(1/2)/3」.

部分逆M矩阵2-弦图的完备问题

本文采用图论的方法对任意阶部分逆M矩阵,当其对应的图为2-弦图时,研究了其逆M矩阵的完备问题。给出了完备定理以及具体完备的算法。

补图为2-点或2-边连通的图的最小特征值(英文)

图的最小特征值定义为图的邻接矩阵的最小特征值,是刻画图结构性质的一个重要代数参数.在所有给定阶数的补图为2-点或2-边连通的图中,刻画了最小特征值达到极小的唯一图,并给出了这类图最小特征值的下界.