IC-平面图的线性荫度

图G的边分解是指将G分解成子图G₁,G₂,...,G_m,使得E(G)-E(G₁)∪…∪.E(G_m),且对任意i≠j,有E(G_i)∩E(G_j)=?.若一个森林的每个连通分支都是路,则称该森林为线性森林.图G的线性荫度la(G)是指使得G可以边分解为m个线性森林的最小整数m.本文证明了Δ(G)≥15的IC-平面图G的线性荫度为[Δ(G)/2],这里Δ(G)是图G的最大度.     

不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界

图G的一个边分解是指将G分解成子图G_1,G_2,…,G_m使得E(G)=E(G_1)=∪E(G_2)∪…∪E(G_m),且对于i≠j,E(G_i)∩E(G_j)=?.一个线性k-森林是指每个分支都是长度最多为k的路的图.图G的线性k-荫度la_k(G)是使得G可以边分解为m个线性k-森林的最小整数m.显然,la_1(G)是G的边色数χ'(G); la_∞(G)表示每条分支路是无限长度时的情况,即通常所说的G的线性荫度la(G).利用权转移的方法研究平面图的线性2-荫度la_2(G).设G是不含有5-圈和相邻4-圈的平面图,证明了若G连通且δ(G)≥2,则G包含一条边xy使得d(x)+d(y)≤8或包含一个2-交错圈.根据这一结果得到其线性2-荫度的上界为[△/2]+4.     

K4-minor-free图的线性2-荫度

图G的线性2-荫度la_2(G)是将G分解为k个边不交的森林的最小整数k,其中每个森林的分支树是长度至多为2的路.本文证明了若G是最大度为Δ(G)的K_4-minor-free图,则la_2(G)≤(Δ(G) 5)/2.     

不含4-,6-圈和相交三角形的平面图的无圈边色数

图G的一个边染色φ:E(G)→{1,2,…,k},若满足任意相邻边都染不同的颜色,且图G不存在双色圈,则称φ为图G的一个无圈k-边染色.图G的无圈边色数χ’_α(G)为使得图G有一个无圈k-边染色的最小正整数k.本文主要证明了对于无4-,6-圈且3-圈与3-圈不相交的平面图G,若Δ(G)≥9,则χ’_α(G)≤Δ(G)+1.     

6-圈至多含一弦平面图的线性荫度

线性森林是指每个连通分支都是路的图.图G的线性荫度la(G)等于将其边分解为k个边不交的线性森林的最小整数k.文中利用权转移方法证明了,若G是一个最大度大于等于7且每个6-圈至多含一条弦的平面图,则la(G)=「(△(G))/2」.     

完全二部图K_(m,n)的线性8-荫度

无向图G的的一个线性k-森林是图G的一个子图,其中该子图的连通分支都是长度不超过七的路.图G的线性k-荫度,记作la_k(G),是图G的边集E(G)能够分解成的线性k-森林的最小数目.本文得到了某些完全二部图K_(m,n)的线性8-荫度.     

Halin图的线性k-点荫度

图G的线性点荫度vla(G)是指V(G)的最小划分数,使得每个点划分集的导出子图为线性森林.G的线性k-点荫度vla_k(G)是指V(G)的最小划分数,使得每个点划分集的导出子图的每个连通分支为长度至多为k的路.1998年,吴建良证明了Halin图的线性点荫度为2.本文在此基础上,证明了对Halin图G,有vla_k(G)=2,其中■     

张量积图的Tutte多项式及其应用

图G为具有m条边的连通图,E(G)={e₁,e₂,…,e_m},H={H₁,H₂,…,H_m}为由m个连通图构成的集合.图G[H]为G与H的张量积图,即对每个i(1≤i≤m),e_i被H_i替代而得到的图.张量积这一图运算包含了多个边替代图运算,例如细分、三角化、钻石化等图运算.本文中,我们给出了G[H]的Tutte多项式的显式表达式,进而得到了细分图、三角化图、钻石化图等运算图的Tutte多项式和生成树数目.     

最大度为4的图的无圈列表边染色

对于图G=(V(G),E(G)),如果一个映射φ:E(G)→{1,2,…,k},使得G中任意相邻的两边e₁,e₂满足φ(e₁)≠φ(e₂),并且G中不含有双色圈,则称φ为G的一个无圈边染色.对于给定的列表分配L={L(e)|e∈E(G)},如果存在图G的一个无圈边染色φ,使得对于任意边e∈E(G),均有φ(e)∈L(e),则称染色φ为G的一个无圈L-边染色.如果对于任意的列表分配L,当对所有的边e∈E(G)满足|L(e)|≥k时,图G均存在无圈L-边染色,那么称G是无圈k-边可选的.使图G无圈k-边可选的最小的正整数k,称为G的无圈列表边色数,用a’_l(G)表示.本文证明了对于最大度△≤4的连通图G,如果|E(G)|≤2|V(G)|-1,则a’_l(G)≤6,扩展了Basavaraju和Chandran文[J.Graph Theory,2009,61(3):192-209]的结果.     

可平面图的线性2-荫度的新上限（英文）

图G的线性2-荫度,记作la_2(G),是使得图G能够被剖分成k个边不交森林的最小正整数k,其中每个森林的每棵树是长度至多为2的路.本文给出了可平面图和没有三角形的可平面图的线性2-荫度的新上界,即证明了:(1)对于一般可平面图,当△≡0,3(mod 4)时,la_2(G)≤[△/2]+9;当△≡1,2(mod 4)时,1a_2(G)≤[△/2]+8;(2)对于不含三角形的可平面图,当△≡0,3(mod 4)时,la_2(G)≤[△/2]+5;当△≡1,2(mod 4)时,la_2(G)≤[△/2]+6;其中△为图G的最大度.     

IC-平面图为第一类图的一个充分条件

图G的一个正常k-边染色是指一个映射Φ:E(G)→{1,2,…,k},使得任意两条相邻的边x,y∈E(G)满足Φ(x)≠Φ(y).使得G具有正常k-边染色的最小正整数k称为图G的边色数,记为χ'(G).著名Vizing定理证明每个简单图G的边色数χ'(G)要么等于最大度Δ(G)要么等于Δ(G)+1.这个定理将所有的图分成了两类:第一类图满足关系式χ'(G)=Δ(G),第二类图满足关系式χ'(G)=Δ(G)十1.本文主要讨论特殊1-平面图的正常边染色问题.1-平面图G是指G能够嵌入到平面上使得G的任意一条边最多被交叉一次.1-平面图G按照上述条件的一种画法称为G的一种1-平面嵌入.所以1-平面图中的每个交叉点w都是由两条边相交所得,从而每个交叉点w都对应着两条相交边,同时也对应着由这两条相交边的四个端点组成的集合ψ(w).如果1-平面图的一个1-平面嵌入中任意两个交叉点w和w'满足ψ(w)∩ψ(w')=Φ,那么称此1-平面图为IC-平面图.在本文中,通过观察分析Δ-临界图和不含相邻弦6-圈的IC-平面图的结构,应用权值转移方法证明了任何最大度为7且不含相邻弦6-圈的IC-平面图G是第一类图.     

最大度大于等于7的平面图的线性荫度

图的染色问题在组合优化、计算机科学和Hessians矩阵的网络计算等方面具有非常重要的应用。其中图的染色中有一种重要的染色——线性荫度,它是一种非正常的边染色,即在简单无向图中,它的边可以分割成线性森林的最小数量。研究最大度△(G)≥7的平面图G的线性荫度,证明了对于两个固定的整数i,j∈{5,6,7},如果图G中不存在相邻的含弦i,j-圈,则图G的线性荫度为[△/2]。     

与任意图正交的［0，ki］m1-因子分解

设G是一个图, k1,…, km是正整数.若图G的边能分解成m个边不交的［0,k1］-因子 F1,…,［0,km］-因子Fm,则称＝F1,…,Fm是G的一个［0,ki］m1-因子分解.如果H是G的一个有m条边的子图且对任意的1≤I≤m有｜E(H)∩E(Fi)｜＝1,则称与H正交.证明了若G是一个［0,k1＋…＋km－m＋1］-图,H是G的一个有m条边的子图,则图G有一个［0,ki］m1-因子分解与H正交.     

一些稀疏图的强边染色（英文）

图G的强边染色是指对图G进行正常边染色使得任意长度为3的路的三条边染不同的颜色.图G的强边色数,记为χ’_s(G),是使得图G是强k边着色的最小正整数kk.2015年,Zang [arXiv:1510.00785]证明了:最大度△(G)=5的图G,χ’_s(G)≤37.本文证明了:最大度△(G)=5且最大平均度小于8/3(或者14/5)的图G,χ’_s(G)≤13 (或者14).另外,本文证明了:最大度△(G)≥3的不含K_2,3-图子式的图G,χ’_s(G)≤4△(G)-6,这个界是紧的.     

一致超图中Berge线性森林的Turán数

设F是一个图,■是一个超图,如果存在一个双射φ:E(F)→E(■),使得?e∈E(F)有e?φ(e),那么称超图■是Berge-F.不含Berge-F作为子超图的n阶r-一致超图所能达到的最大边数称为Berge-F的Turán数,记作ex_r(n,Berge-F).线性森林是指连通分支全是路或者孤立顶点的图.设■_n,k是一类含有n个顶点k条边的线性森林图族.本文研究了r-一致超图中Berge-■_n,k的Turán数.当r≥k+1和3≤r≤■(k-1)/2■-1时,分别确定了ex_r(n,Berge-■_n,k)的精确值;当■(k-1)/2■≤r≤k时,给出了ex_r(n,Berge-■_n,k)的上界.     

给定P3的无桥图的定向直径

设G是一个无向多重图,G的定向直径是指G的所有强连通定向中直径的最小值.Dankelmann,Guo,Surmacs [J.Graph Theory,2018,88:5-17]证明了n阶无桥图G的定向直径至多为n-Δ+3,这里Δ是G的最大度.设H是G的一个生成子图,定义■,利用上述结论他们还证明了,给定边e的无桥图G的定向直径至多为n-|N_G(e)|+5,以及给定无桥子图H的无桥图G的定向直径至多为n-|N_G(H)|+3.设P₃=uvw是G的一条长为2的路.易见P3包含两条边且这两条边均是P3的桥.本文利用将一条路收缩为一点的方法证明了给定P3的无桥图G的定向直径的上界为n-|N_G(P₃)|+5.特别地,若P3在一个4圈上或P3不在一个圈上但uv,vw分别在一个3圈上,定向直径至多为n-|N_G(P₃)|+4.最后举例说明了上述上界是紧的.     

具有特定纯净效应折中设计的若干理论及构造

许多因析试验中,试验者只关心指定的一部分因子效应的估计效果.针对此类问题,Addelman(1962)首次提出了折中设计的方法,并定义纯净折中设计以保证指定的因子效应被有效地估计出来,但此类纯净折中设计的分辨度限定Ⅲ为Ⅳ.本文研究了四类全新的折中设计,指定因子效应的集合分别记为{G₁;G₁×G₁}、{G₁;G₁×G₁;G₂×G₂}、{G₁;G₁×G₁;G₁×G₂}和{G₁;G₁×G₂}.相应地,可以定义四种类型的纯净折中设计,即指定因子效应全部纯净的设计.本文研究四类纯净折中设计的存在性和结构特性,给出一些理论结果和具体的构造方法.构造结果表明新型的纯净折中设计的分辨度为Ⅲ或Ⅳ,并且与Addelman(1962)提出的纯净折中设计相比具有更多的纯净两阶交互效应.     

太阳图与路的笛卡儿积图的任意可分性（英文）

一个阶为n的图G称为是任意可分的(简作AP),如果对于任一正整数序列τ=(n₁,n₂,…,n_k)满足n=n₁+n₂+…+n_k,总是存在顶点集V(G)的一个划分(V₁,V₂,…,V_k)满足:对于i∈[1,k],|V_i|=n_i,且子图G|V_i|是图G的V_i导出的一个连通子图.我们用S~*=S(n;m₁,m₂,…,m_n)来表示最大度△(S~*)=3的太阳图.本文讨论了图S~*P_m(m≥3)的任意可分性.     

围长至少为6的平面图的邻点可区别边染色

邻点可区别边染色是指图G有一个正常边染色且任意两个相邻顶点的颜色集合不相等.邻点可区别边色数是指使图G有一个邻点可区别边染色的最小颜色数值,记作χ_α’(G).本文证明了:若图G是围长至少为6的正常平面图,则有χ_α’(G)≤max{6,△(G)+1}.     

若干圈限制平面图的星边染色

图G的星边染色是指G的一个正常边染色,使得G中任一长为4的路和长为4的圈均不是2-边染色的.图G的星边色数χ’st(G)表示图G有星边染色的最小颜色数.设G是最大度为Δ的平面图,我们证明了:(1)若G不含4-圈,则χ’st(G)≤[1.5Δ]+15;(2)若g≥5,则χ’st(G)≤[1.5Δ」+10;(3)若g=7,则χ’st(G)≤[1.5Δ」+6.