关于图的谱半径的一个改进上界

通过对图的邻接矩阵结构的分析和讨论，得到了一个关于图的谱半径的一个新的上界，从而改进的几个已知的结果。     

Cycles Through Many Vertices of Given Subsets in 1-Tough Graphs

设Ｇ是ｎ阶１－坚韧图，Ｘ是Ｇ的顶点子集合，定义α（Ｘ）＝ｍａｘ｛｜Ｓ｜｜Ｓ是诱导子图Ｇ［Ｘ］中的顶点独立集｝，σｋ（Ｘ）＝ｍｉｎ｛ｋｉ＝１ｄ（ｘｉ）｜｛ｘ１，ｘ２，…，ｘｋ｝是独立集｝和ｃ（Ｘ）＝ｍａｘ｛｜Ｖ（Ｃ）∩Ｘ｜｜Ｃ是Ｇ中的圈｝。我们得到如下主要结果：设Ｇ是ｎ阶１－坚韧图，并且σ３（Ｘ）≥ｎ，则ｃ（Ｘ）≥ｍｉｎ｛｜Ｘ｜，｜Ｘ｜＋δ（Ｘ）－α（Ｘ）＋１｜，并且这下界是最好的，这里δ（Ｘ）是不小于１３σ３（Ｘ）的最小正整数．     

迭代法的并行化

迭代法是解方程组的主要方法之一。本文利用图论知识讨论迭代法并行执行的可能性问题。     

关于可解群的一类特征标图

在可解群Ｇ的特征标图的中心ＺΓ（Ｇ）满足一定条件时，给出了Ｇ的特征标子图Γ（Ｇ）－ＺΓ（Ｇ）的连通分支数，同时给出了一类拟ＰＰＣ（χ０，ｐ，ｑ）群的基本结果     

Halin图的无圈边着色

设f是图G的一个正常边着色，若在f下G中没有2-色圈，则称f是图G的一个无圈边着色，其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图，无圈边色数不超过其最大度加2。本文证明了该猜想对Halin图成立，且当Δ≤4时，其色数不超过5；当Δ≥5时，其色数等于最大度。     

调和的五圈图

设v1,v2,…,vn是n阶图G的顶点,d(vi)表示顶点vi的度.如果(d(v1),d(v2),…,d(vn))T是图G的邻接矩阵的一个特征向量,则说图G是调和的.证明了恰有一个4-调和5圈图,结合文献[6],确定了所有调和的5圈图.     

笛卡尔积图的2-距离色数

图G(V,E)的2-距离染色是指正常的顶点染色,且距离不大于2的任意两个顶点着不同的颜色.给出了笛卡尔积图的一个2-距离色数的可达界,即Δ(G) Δ(H) 1≤χ2(G×H)≤2χ(G)χ2(H),以及一些特殊笛卡尔积图的2-距离色数,说明此界可达.     

BSn,ECn和FCn的对称性

对称性是图作为网络模型的重要性质.而网络设计者关注较多的是那些同距离有关的对称性.这是因为路径问题是网络研究的核心问题.BSn,ECn和FCn是三类常用于互联网络的Cayley图.1993年,lakshm ivarahan等人提出了一些公开问题.其中包括BSn,ECn和FCn的距离正则性.在本文中,对于BSn,ECn和FCn我分别定义了一些参数称为"改良的交叉数".并且证明了这三类图的确具有依赖于距离的对称性.这说明在这三类图中寻找一个不依赖于点的路径是可行的.     

关于拓扑指标Z2(G)研究的一个结论

分子的化学与物理性能一般能用分子图的拓扑指标统计地反映出来．反过来，通过对分子图的拓扑指标的研究，以期得到理想的分子具有重要的理论价值和应用背景．文中解决了两个问题：1．对于任意的自然数Z，是否都存在一个简单连通图G，使得Z2(G)=Z?2．对于任意的自然数Z，是否都存在树T，使得T2(T)=Z?     

平面图选择控制集问题的复杂性分析及算法设计

研究平面图的选择控制集问题．通过PX3C(planar exact cover by 3-sets)到平面图控制集的变换，证明了平面图的控制集问题是NP完全的，从而得到平面图的选择控制集问题的NP完全性．同时提出了一个基于遗传算法的求平面赋权图的选择控制集的近似算法．