门槛图与度极大图(英文)

证明了门槛图与度极大图是一类图的两种不同说法，同时用图的对角限制极左矩阵刻画这一类图的结构．

门槛图中的一些优化问题

门槛图是一类结构比较特殊的图,本文给出了它的一个标准表示形式,并在此基础上建立了一个好的算法来构造它的中心树。利用中心树的结构性质,用多项式时间算法解决了这类图的一些优化问题,包括最大团、最大独立子集问题,染色问题,最小边割集问题和哈密尔顿性问题。

两类联图的PI不变边

设G=(V(G),E(G))是一个简单连通图。图G的PI指标定义为PI(G)=∑_(e=uv∈E(G))[n_(1)^((e|G))+n_(2)^((e|G))],其中n_(1)^((e|G))是图G中到点u的距离比到点v的距离小的点的数目,n_(2)^((e|G))是图G中到点v的距离比到点u的距离小的点的数目。如果PI(G-e)=PI(G),那么边e称为图G的PI不变边。本文中分别讨论门槛图和轮图存在PI不变边的条件。

一类图的广义特征多项式

首先定义了一类新图——类似门槛图,然后结合算法设计得到了这类图的广义特征多项式(即Φ-谱),从而推出了一类门槛图的Φ-特征多项式及其谱。作为应用,还构造了一些Φ-同谱无穷类。

关于第二类Zagreb指数猜想的一个证明

设G是一个n阶简单图.G的第二类Zagreb指数定义为M_(2)(G)=∑ij∈E(G)d_(i)d_(j).其中d_(i)表示顶点i的度.Xu等(2014)提出了一个关于第二类Zagreb指数的猜想:在所有阶数为n、边数为m的图中,M_(2)(G)最大的图是拟完全的.借助于门槛图的Ferrers表的性质,本文将上述猜想转化为组合矩阵论优化问题,并给出该猜想的一个代数证明.