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的最大度.     

1-平面图的线性荫度

图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)≥25的1-平面图G的线性荫度为[Δ(G)/2],这里Δ(G)是图G的最大度.     

交叉数为2且因子图为路的笛卡尔积图

M.Kle??和J.Petrillová刻画了当G1为圈且cr (G1G2)=2时,因子图G1和G2所满足的充要条件.在此基础上,该文进一步刻画了在cr (G1G2)=2的前提下,当G1=P4,或者G1=P3且△(G2)=4时,因子图G2应满足的充要条件.     

关于交叉数为2的联图

确定图的交叉数是NP-完全问题.Kuratowski定理刻画了平面图的结构特征,而对于交叉数为k(k≥1)的非平面图G的结构特征刻画,目前相关结果甚少.对于交叉数为1的联图G_1∨G_2,我们已经刻画出因子图G_1和G_2满足的充要条件.本文刻画了当△(G_2)≠3且cr(G_1∨G_2)=2时因子图G_1和G_2须满足的充要条件.     

最大度为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]的结果.     

不含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.     

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

一个阶为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)的任意可分性.     

张量积图的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多项式和生成树数目.     

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

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

NIC-平面图的存活率

假设火在图G的某个顶点燃起,消防员每步最多可以防护k个顶点,然后火蔓延到所有未被防护的邻点.当火随机地在图G的一个顶点燃起时,消防员最多能防护的顶点数的平均比率称为图G的k-存活率,记为ρ_k(G).如果图G能画在平面上使得每两对交叉边至多有一个公共顶点,那么称G是NIC-平面图.本文证明了NIC-平面图G有ρ₅(G)> 1/73.     

图的上可嵌入性与圈中顶点度

本文利用非上可嵌入图的充要条件,结合圈中顶点最大度与图的上可嵌入性之间的关系,得到了下两个结果:(1)设G是2-边连通简单图,若对G中任意圈G,存在点x∈C满足,d(x)>|V(G)|/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.(2)设G={x,y;E}为简单二都图,且是2-边连通的. |x|=m,|Y|=n(m,n≥3),若对G中任意圈C,存在点x∈C且x∈X满足d(x)>n/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.     

强乘积图的最小强半径（英文）

A strong product graph is denoted by G₁?G₂,where G₁ and G₂ are called its factor graphs.This paper gives the range of the minimum strong radius of the strong product graph.And using the relationship between the cartesian product graph G₁ ×G₂ and the strong product graph G₁?G₂,another different upper bound of the minimum strong radius of the strong product graph is given.     

U(4,Z)的自同构群(英文)

In this paper,the automorphism group of G is determined,where G is a 4 × 4 upper unitriangular matrix group over Z.Let K be the subgroup of AutG consisting of all elements of AutG which act trivially on G/G,G /ζG and ζG,then （i） InnG ■ K ■ AutG;（ii） AutG/K≌=G₁×D₈×Z₂,where G₁=(a,b,c|a⁴=b²=c²=1,a^b=a^-1,[a,c]= [b,c]=1 ;（iii） K/Inn G≌=Z×Z×Z.     

多扇图的Pebbling数和Graham猜想

图G的pebbling数f(G)是最小的整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把1个pebble移到任意一个顶点上,其中一个pebbling移动是从一个顶点处移走两个pebble而把其中的一个移到与其相邻的一个顶点上。Graham猜想对于任意的连通图G和H有f(G×H)f(G)f(H)。多扇图F_n1,n2,…,nm是指阶为n₁+n₂+…+n_m+1的联图P₁∨(P_n1∪P_n2∪…∪P_nm)。本文首先给出了多扇图的pebbling数,然后证明了多扇图F_n1,n2,…,nm具有2-pebbling性质,最后论述了对于一个多扇图和一个具有2-pebbling性质的图的乘积来说,Graham猜想是成立的。作为一个推论,当G和H都是多扇图时,Graham猜想成立。     

给定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.最后举例说明了上述上界是紧的.     

关于分数因子两个开问题的解答

本文指出极小连通二部分数1-因子不一定是极小2-连通图.研究了σ₂（G）与分数k-因子存在性之间的关系,指出存在一个特例在满足阶数n≥4k-5,δ（G）≥k且σ₂（G）≥n条件下,图G不存在分数k-因子.     

图的非负广义邻接矩阵的谱半径的一些界（英文）

顶点数为n,边数为m的简单图G的非负广义邻接矩阵定义为U(G)=γAA(G)+γ_II(G)+γ_JJ(G)+γ_DD(G),其中γ_A,γ_I,γ_J,γ_D是一些非负实数,A(G)是图G的邻接矩阵,D(G)=diag(d₁,d₂,…,d_n),I(G)是单位矩阵,J(G)是全1矩阵.本文得到了谱半径ρ_U(G)的一些界,并刻画了达到这些界时的极图.此外还得到了ρ_Aα(G)的新界以及ρ_A(G),ρ_L(G)和ρ_Q(G)的已知界.     

给定直径的单圈图的边修正Szeged指标的下界

连通图G的边修正Szeged指标Sz_e^*(G)定义为■,其中m_u(e|G),m_v(e|G),m₀(e|G)分别是G中到u点比到v点距离近的边的数目、到v点比到u点距离近的边的数目、以及到u,v两点距离同样近的边的数目.本文通过变换和计算得到了给定直径的单圈图的边修正Szeged指标的下界,并刻画了达到下界的极值图.     

一个特殊6点图Q与nK_1,P_n及C_n的联图交叉数

图的交叉数是图的一个重要参数,研究图的交叉数问题是拓扑图论中的前沿难题.确定图的交叉数是NP-难问题,因为其难度,能够确定交叉数的图类很少.通过圆盘画法途径,确定了一个特殊6点图与n个孤立点nK_1,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+2[n/2],cr(Q+P_n)=Z(6,n)+2[n/2]+1及cr(Q+C_n)=Z(6,n)+2[n/2]+3.     

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

图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,这个界是紧的.