独立数的另一类关系

本文研究了图的独立数与边独立数、独立数与全独立数、边独立数与全独立数、图的独立数与其补图边独立数、图的独立数与其补图的全独立数、图的边独立数与其补图全独立数之间的关系,得到了不可改进的结果     

倒距离矩阵的谱半径(英文)

本文刻画了在分别具有给定点连通度、边连通度、色数和独立数的n阶图中具有最大倒距离矩阵谱半径的图.     

若干图类的Wiener指数的极值

一个图的Wiener指数是指这个图中所有点对的距离和.Wiener指数在理论化学中有广泛应用. 本文刻画了给定顶点数及特定参数如色数或团数的图中Wiener指数达最小值的图, 同时也刻画了给定顶点数及团数的图中Wiener指数达最大值的图.     

树图对完全图的多色Ramsey数

首先证明了关于一般图的多色Ramsey数的一个下界,该下界是一类星图对完全图的多色Ramsey数的精确下界;其次证明了关于星图对完全图的多色Ramsey数的上界,该上界是一类星图对完全图的多色RamSey数的精确上界;最后证明关于树图对完全图的多色Ramsey数的上界.     

乘积图的全色数

本文得到了有关乘积图的全色数的一些结果，并利用这些结果证明了Mesh图和Tours-图均满足全色数猜想．特别，几乎所有的Mesh-图都是第一类图．     

Halin图的Alon-Tarsi数

图G的Alon-Tarsi数,是指最小的k使得G存在一个最大出度不大于k-1的定向D满足G的奇支撑欧拉子图的个数不同于偶支撑欧拉子图的个数.通过分析Halin图的结构,利用Alon-Tarsi定向的方法确定了Halin图的Alon-Tarsi数.     

最大度为5的图的Alcuin数

1000多年前,英国著名学者Alcuin曾提出过一个古老的渡河问题,即狼、羊和卷心菜的渡河问题.最近,Prisner和Csorba等人把这一问题推广到任意的"冲突图"G=(V,E)上,考虑了一类情况更一般的运输计划问题.现在监管者欲运输V中的所有"物品/点"渡河,这里V的两个点邻接当且仅当这两个点为冲突点.冲突点是指不能在无人监管的情况下留在一起的点.特别地,Alcuin渡河问题可转化成"冲突路"P_3上是否存在可行运输方案问题.图G的Alcuin数是指图G具有可行运输方案(即把V的点代表的"物品"全部运到河对岸)时船的最小容量.最大度为5且覆盖数至少为5的图和最大度Δ(G)≤4且覆盖数不小于Δ(G)-1的图的Alcuin数已经被确定.本文给出最大度为4且覆盖数不超过2和最大度为5且覆盖数不超过4的图的Alcuin数.至此,最大度不超过5的图的Alcuin数被完全确定.     

点删除下的图的$A_\alpha$特征值的交错性

设$G$为具有顶点集$V$, 边集$E$的简单图, 本文给出了图$G$与其子图$G-U$的$A_\alpha$特征值的交错不等式, 其中$U\subset V$. 作为应用, 我们利用该交错不等式导出了一些关于图的独立数, 点覆盖数, 哈密尔顿性及支撑数的$A_\alpha$ 谱条件.     

关于Mycielski图循环色数的猜想

通过引进Mycielski图点集的一类特殊划分,利用该划分在Mycielski图循环着色中的特点改进了如下猜想:完全图的Mycielski图的循环色数等于它的点色数.     

匹配数与控制数相等的图的结构性质

我们分别用γ(G)，β(G)和α(G)表示图G的控制数、匹配数和覆盖数，对任意连通图，有γ(G)≤β(G)≤α(G)成立，1998年，Randerath和Volkmann给出了控制数等于覆盖数的图的特征，本文首先证明了匹配数与控制数相等的图其最小度不超过2，而后给出了最小度为2的图的结构性质。     

Mycielski图的循环色数

通过引入一类点集划分的概念,研究了Mylielski图循环染色的性质,证明了当完全图的点数足够大时,它的Mycielski图的循环色数与其点色数相等.     

在Δ≤3的图中上独立数和上无赘数的关系

G（V，E）是一个图。β，IR分别是图G的独立数，上无赘数。这篇文章证明文章［6］中提出的一个猜想.     

图的点覆盖数与其Laplace谱半径

本文讨论图的点覆盖数与图的 Laplace谱半径的关系 ,利用特征向量的技巧得到由图的 L aplace谱半径所确定的关于图的点覆盖数的紧的界     

图的平面Turán数和平面anti-Ramsey数

在所有顶点数为$n$且不包含图$G$作为子图的平面图中,具有最多边数的图的边数称为图$G$的平面Turán数,记为$ex_{_\mathcal{P}}（n,G）$。给定正整数$n$以及平面图$H$,用$\mathcal{T}_n （H）$来表示所有顶点数为$n$且不包含$H$作为子图的平面三角剖分图所组成的图集合。设图集合$\mathcal{T}_n （H）$中的任意平面三角剖分图的任意$k$边染色都不包含彩虹子图$H$,则称满足上述条件的$k$的最大值为图$H$的平面anti-Ramsey数,记作$ar_{_\mathcal{P}}（n,H）$。两类问题的研究均始于2015年左右,至今已经引起了广泛关注。全面地综述两类问题的主要研究成果,以及一些公开问题。     

三类笛卡尔积图的关联色数

图的关联色数的概念是 Brualdi和 Massey于 1 993年引入的 ,它同图的强色指数有密切的关系 .Guiduli[2 ] 说明关联色数是有向星萌度的一个特殊情况 ,迄今仅确定了某些特殊图类的关联色数 .本文给出了完全图与完全图、圈与完全图、圈与圈的笛卡尔积图的关联色数。     

分子图的Zagreb拓扑指标的逆问题

研究了化学分子图的Zagreb指标的逆问题，解决了对于给定的怎样的数存在分子图，其Zagreb指标值等于该数的问题，对n个顶点m条边的简单连通图，给出了其具有最小Zagreb指标值的充分必要条件，并给出了其具有最大Zagreb指标值的必要条件，为利用计算机搜索具有给定Zagreb指标值的所有分子图界定了顶点数和边数的范围，从而提高了计算机搜索的效率，这在组合化学中具有重要的意义。     

关于偏序集相关联图的色数

对于每一个含有最小元素0的偏序集（P,≤）可以得到一个与其关联的图G（P）.本文主要通过代数的方法研究了所得关联图G（P）的性质,证明了如果G（P）的色数和团数是有限的,那么色数和团数都仅比P的极小素理想的个数大1.     

用Paley图计算对角Ramsey数下界的新方法

本文研究了对角Paley数的下界问题.利用一个新发现的Paley图的自同构,给出了计算Paley图团数的一个新方法,获得了2个对角Rasey数的新下界:R(20,20)≥18877,R(21,21)≥25949.     

色数等于选择数的4-正则图

设Hn(n≥5)表示一个图:以1,2,．．．,n为顶点,两个点i和j是相邻的当且仅当|i-j|≤2,其中加法取模n．这篇文章证明了,Hn的色数等于它的选择数．结果被用于刻画最大度至多2的图的列表全色数．     

给定匹配数和独立数时图零度的上界

设G是一个有n个点的简单图,分别记η(G),m(G)和α(G)为图G的零度、匹配数和独立数.设θ(G)是一个非负整数,定义为使图G成为二部图至少需要从G的边集中删去的边数.本文运用二部划分运算,证明了对于有n个点并且不含有圈长为2的倍数的圈为子图的简单图G,有η(G)≤n-2m(G)+20(G)和η(G)≤2α(G)+2θ(G)-n.