具有极值广义连通指数的似星树

设T是一棵似星树,即其中仅有一个顶点的度数大于2的树,并设其中最大的顶点度数为m,T的广义连通指数为R_a(t)∑uv∈E(T),其中d(u)为树T中顶点u的度,α是任意实数.通过图的变换,证明了似星树的广义连通指数Rα(T)是e1m(T)的递减函数,e1m(T)是T中连接一个1度顶点与m度顶点的边数;并由此刻画了具有最大、最小广义连通指数的似星树.     

最小度生成树的最大度算法

最小度生成树问题是一个NP难问题.给出了求最小度生成树的一个直观近似算法:找到图G的最大度,从其所在的基本圈上删掉1条与其关联的边,如此循环,直到图G的最大度不在任何基本圈上,如还有其它基本圈,删掉圈上的1条边,得到1棵生成树.这种算法得到的生成树的最大度数比最优解的度数至多大1.     

极大平面图中二色树子图的一个必要条件

极大平面图G=(V,E)中的一个二色树子图T=(Vt,Et),其Vt在G中导出子图为树,并且图G存在至少一个四着色C,使T是该四着色一个二色子图的一个连通支.本文证明了Vt的点次和为偶数是它成为二色树子图的必要条件.     

均衡二部图中一个有限制条件的2-因子

本文证明了在2n阶的均衡二部图中,若满足2n大于正数sk,其中s大于等于3,k大于等于1.如果图C中任意两点的度数之和的最小值满足文章中所给的条件,则C有一个2-因子至少含一个长至少为2s的圈.     

无爪图的支撑k-端点树的存在性

树T中度为1的点称为叶子,叶子数目不超过k的树称为k-端点树.图中存在一个哈密尔顿路,说明图中存在恰好含有两个叶子的支撑树.自然就有了关于哈密尔顿路问题的一个推广：考虑图中至多有k个叶子的支撑树即支撑k-端点树的存在性问题.通过控制集参数,确定了连通无爪图中存在支撑k-端点树条件.     

无爪图与分裂图的L(d,1)-T标号

给定一个简单连通图G及其一棵支撑树T,图G的1个L(d,1)-T标号即一个标号函数g满足:①G的任意2个相邻点的标号至少差1;②T上任意两个相邻点的标号至少差d;③G上任意两个距离为2的点的标号至少差1.本文研究了无爪图与分裂图的L(d,1)-T标号并给出了Tld,T(G)一个界.     

关于恰有一个圈的连通简单图的图序列

本文证明了只有一个圈的连通简单图的图序列的充要条件。设 G 是一个图,它有 n 个顶点 a_1,a_2,…,a.d(a_i)表示在 G 中与 a_i关联的边数。序列d(a_1),d(a_2),…,d(a(?))称为 G 的度序列。如果 G 为一简单图,那么它的度序列称为图序列。     

Super-Euler迭线图的特征刻划

图中端点度数不是２而内点的度数是２的路叫做枝。文中证明了一个连通图Ｇ的ｎ次迭线图Ｌ＾ｎ（Ｇ）是Ｓｕｐｅｒ－Ｅｕｌｅｒ图的充要条件是Ｇ有一个包含Ｇ的每个度至少为３的项点的子图Ｈ,满足：Ｈ的每个顶点都是偶度;Ｈ的孤立顶点在Ｇ中度至少为３;Ｈ的任何连通分支与Ｈ的其它连通分支在Ｇ中的距离至多是ｎ;对于Ｇ中不在Ｈ中的枝的长度至多为ｎ＋１,对于Ｇ中有端点度为１的枝的长度至多为ｎ。     

树的直径和倒对偶度

图的直径是重要的不变量,但计算它是困难的。任给一个连通图G,它的各点的度也就明显可知了。设u是G中的任一点,我们用u点的对偶度来表示u点邻域中各点度数的平均数。进一步,我们把G中所有点的对偶度的倒数的和称为图G的倒对偶度。当图的邻接矩阵给出时,倒对偶度能方便地计算出来。文中利用倒对偶度建立了树的直径的最好可能的上界。     

有向笛卡尔积图的k-限制弧连通度

笛卡尔积图是大型互联网络最重要的数学模型之一.有向图的k-限制弧连通度是弧连通度和限制弧连通度的推广,可用于度量网络的可靠性.强连通有向图D的弧子集S被称为D的一个k-限制弧割,若D-S有一个顶点数至少为k的强连通分支D_1,使得D-V(D_1)包含一个顶点数至少为k的连通子图.若这样的一个弧割存在,则称D是λ~k-连通的.D中最小k-限制弧割所含的弧数称为D的k-限制弧连通度,记做λ~k(D).在有向笛卡尔积图中,推广2-限制弧连通度的结论到k-限制弧连通度,得到有向笛卡尔积图的k-限制弧连通度的上界和3-限制弧连通度的下界,并用例子说明所得界是紧的.     

关于图同构复杂性的一点补充

在图G=(V，E)中，删除其度数最大的顶点及其关联的边，在余下的子图中，如法炮制，直至余下的子图为零图．设所删除的这些顶点x1，x2，…，xi的度数依次为P1，P2，…，Pl，称序列P1，P2，…，Pl为图G的度序列；xi(1≤i≤l)关联的边的另一端点在G中的度数的集合称为顶点五关联的度集合．通过计算、比较两图的度序列、被删除的顶点的度数以及它们关联的度集合，证明两图同构问题的复杂度是多项式的．     

图的度平方和的下界

对图的度平方和的下界进行了讨论.用G=(V,E)表示一个具有n个点e条边的简单图,并且点的度数分别为d1,d2,…,dn.利用均值不等式及图中度序列的关系,给出了图G的度平方和的两个下界,并确定了达到这两个下界的极图.同时也给出了度平方和下界的简单应用,用它们来确定一个图及其补图中三角形的总个数.     

条件染色正常图的几个充分条件

给定正整数r,图G的一个r-条件染色是G的顶点的一个正常染色,使得G中任意度数为d(v)的顶点v,其邻域中至少出现min{r,d(v)}种不同的颜色。若图的r-条件色数等于色数,则称图为r-正常的。给出了判断一个图G为正常图的一些充分条件,并用实例说明了这些条件并非必要的。     

三类不含拉普拉斯特征值1的树

设A(G)为图G的邻接矩阵,D(G)为图G的度对角矩阵,称L(G)=D(G)-A(G)为图G的拉普拉斯矩阵,则特征多项式?_G(μ)=det(μI-L(G))的所有根称为图G的拉普拉斯特征值。一个端点的度不小于3,另一个端点的度等于1的路,被称为外部路。对于任意图G,如果G的外部路上包含P₃子图,则删除P₃不影响图G中拉普拉斯特征值1的重数。通过递归删除外部路上的P₃,刻画了不含拉普拉斯特征值1的星型树、双星树和三星树。     

随机扰动有向图的泛圈性（英文）

Dirac定理指如果n个顶点的图G最小度至少为n/2，则G包含一个哈密尔顿圈. Bohman等引入了随机扰动图模型并证明了对任意正常数α和最小度至少为αn的图H，存在一个仅依赖于α的常数C使得对任意p≥C/n H∪G_n,p是几乎渐进肯定哈密尔顿的。本文考虑了随机扰动有向图模型，证明了对任意α=ω{(logn/n)^1/4}和d∈{1, 2}，一个最小度至少αn的n点有向图和随机d正则有向图是几乎渐进肯定泛圈的。更进一步，给出了一个在这种随机扰动有向图中构造任意长度有向圈的算法。     

4连通图中生成树上的可去边

图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割端片的性质给出某些4连通图中在特定子图上可去边的分布情况,得到了最小度至少为5或围长至少为4的4连通图中在其生成树上存在至少两条可去边;同时也得到了最小度至少为5的4连通图中在其生成树外存在至少两条可去边.     

Wn⊙Pm和Cn⊙Sm的r-hued染色

图G和H的Corona乘积图记为G⊙H,它是复制一个图G以及复制|V(G)|个图H,把图G的第i个顶点跟复制的第i个图H的每个顶点相连.图G的(k,r)-染色是用k种颜色对图G进行正常染色，使得点v的所有邻点至少染min{r,d(v)}种不同的颜色，其中d(v)是图G中顶点v的度数.把图G的具有(k,r)-染色的最小正整数k称为r-hued色数，用χ_r(G)表示，通过对r-hued染色的定义，得到W_n⊙P_m和C_n⊙S_m的r-hued色数.     

NIC-平面图中轻风筝的存在性

将K_1,3任意两点连接起来所形成的图形称为风筝.设H是一个连通图,■是一个图类,如果对任意的■包含一个子图K,K同构于图H,且满足■那么称H为■的轻子图.如果H是一个风筝,就称H为轻风筝.利用权转移方法研究了NIC-平面图中轻风筝的存在性,证明了每个最小度至少为5并且最小边度至少为11的NIC-平面图含有一个最大度至多为29的风筝.     

关于二分图的F-Hamilton性

设G是一个简单图,任意e∈E（G）,定义e=uv在G中的度d（e）=d（u）＋d（v）,其中d（u）和d（v）分别为顶点u和v在G中的度数。设F是二分图G的一个1-因子,如果G中有包含F的Hamilton圈,则称G是F-Hamilton的;给出了二分图是凡Hamilton的一个新的充分条件。     

无指定相交圈的非负特征图的列表点荫度

对于图的任一顶点集的划分,并使每个划分的导出子图均为无圈图的最小的划分基数称为图的顶点荫度.对于图G的每个顶点给定一个列表基数至少为k的颜色集合,对于图的任一染色,若每个顶点的颜色均选择与其关联的颜色集,使得每种颜色类的导出子图是一个无圈图的最小的基数k称为图的列表点荫度.证明了每个无6圈和相交i,j-圈(i,j∈{3,4})的非负特征图的列表顶点荫度为2,即为4列表可选色.