Hamilton线图中的泛圈性

对于图Ｇ的边ｅ＝ｕｖ，定义ｄ（ｅ）－ｄ（ｕ）＋ｄ（ｖ），这里ｄ（ｕ）和ｄ（ｖ）分分别表示ｕ和ｖ的度，该文的主要结果是：对阶为ｎ（ｎ≥４０）的简单连通图Ｇ，如果对Ｇ中任意两条边距离为２的边ｅ１，ｅ２都有ｄ（ｅ１）＋ｄ（ｅ２）≥ｎ，并且线图Ｌ（Ｇ）是Ｈａｍｉｌｔｏｎ的，则Ｌ（Ｇ）是泛圈的，并且条件Ｌ（Ｇ）是Ｈａｍｉｌｔｏｎ是必要的。     

线图泛圈性的一个充分条件

设 e=uv 是 G 中住一条边,e 的次数 d(e)=d(u)+d(v),其中 d(u)和d(u)分别为顶点 u 和 v 在 G 中的度数。本文的主要结果是:设 G 是几乎无桥的,n≥11阶简单连通图,若对任意相距为1的两边 e_0和 e_1,d(e_0)+d(e_1)≥2n-5,则 G 的线图 L(G)是泛圈的。     

关于泛圈线图的注记

设Ｇ是包含圈的简单图，如果对于Ｇ的任意两条边ｅ，ｆ都有ｄ（ｅ，ｆ）≤１，那么Ｇ的线图是泛圈的或是长为４或５的圈。本注记以一类图说明所给条件是最好可能的。     

完全二部有向图的迭代线图的泛偶圈性

泛圈性是网络拓扑结构（图或有向图）的一个重要拓扑性质,也是度量网络性能优劣的一个重要指标。LCBD（d,n）是一类稠密的二部有向图,它是完全二部有向图K_（d,d）的（n-1）重迭代线图。本文研究了LCBD（d,n）的泛偶圈性,通过LCBD（d,n-1）的Euler回构造了一个2d~n位的序列,证明了LCBD（d,n）是泛偶圈的,并且当n是偶数时,LCBD（d,n）是点n泛偶圈的,当n是奇数时,是点（n＋1）泛偶圈的。     

线图泛圈性的一个充分条件

本文的主要结果是：设G是n≥60阶连通图，且G是Hamilton图．若G满足下列条件之一（1）若g＝3且■e∈E（G），有d（e）≥（2n-9）／5，（2）若g≥4且■e1，e2∈E（G），e1与e2不相交，有d（e1）＋d（e2）≥2（2n-9）／5，则L（G）是泛图的。     

线图上次泛圈性的两条独立边的度和条件

给定一个n（n≥72）阶图G,满足q1（G）=min{d（u）＋d（v）：uv∈E（G）}≥8,得出结论：若围长g（G）≥5且q2（G）=min{d（ei）＋d（ej）：ejej E（L（G））且ei,ej∈E（G）}〉2√2n=1时,L（G）是次泛圈图;若围长g（G）≥4且q2^2（G）-2q2（G）〉8n时,L（G）是次泛圈图,而且2√2n＋1,8n这两个界都是最好可能的。     

线图上泛圈性的两个独立点的度和条件

设G是阶数为n 51的简单连通图,满足周长g(G)4,且2δ(G)(2n-9)/5。若G是哈密顿图,则其线图L(G)是泛圈图。     

每个直径不大于2的图的线图是泛圈的或4圈或5圈

图的直径是指图的顶点间的最大距离，该文证明了每个直径不大于２的图的线图是泛圈的或是４圈或５图，且所给条件是最好可能的。     

图的控制数与其补图覆盖数的关系

本文研究了图的控制数、边控制数与其补图覆盖数间的关系．获得了某些重要不等式，且均为界可达。     

循环图及单圈图的有效控制集与完美控制集

图的完美控制集和有效控制集是两类特殊的控制集．通常要判断一个图是否存在有效控制集是困难的．该文证明了无向循环图一定存在有效控制集．此外，给出了单圈图的完美控制数与其阶数的关系．     

关于图中给定端点的Hamilton—路及D—路

设Ｇ是有限无向简单图。｛ａ,ｂ｝等于包含于Ｖ（Ｇ）,Ｎ［ａ］＝Ｎ（ａ）∪｛ａ｝,令Ｊ（ａ,ｂ）＝｛ｕ│ｕ∈Ｎ（ａ）∩Ｎ（ｂ）且Ｎ（ｕ）等于包含于Ｎ［ａ］∪Ｎ［ｂ］｝。Ｇ＾＊称为Ｇ的部分平方图：Ｖ（Ｇ＾＊）＝Ｖ（Ｇ）,Ｅ（Ｇ＾＊）＝Ｅ（Ｇ）∪｛ａｂ│ａｂ不属于Ｅ（Ｇ）,Ｊ（ａ,ｂ）≠Φ｝。设Ｇ是（ｋ＋１）－连通图（ｋ≥２）,｛ｕ１,ｕ２｝等于包含于Ｖ（Ｇ）。本文主要结论：（ａ）设Ｇｗ是Ｇ中添加新顶点     

图的谱半径和泛圈性

设G=(V,E)是一个n阶m条边的简单连通图,μ(G)为图的邻接矩阵的最大特征值。本文利用图的谱条件讨论了图的泛圈性,证明了n(n≥5)阶图G,如果μ(G)n-2,则G是泛圈图除非G=Kn-1+e。     

一类图中D—闭迹存在的充分条件

设G是一个简单图,(?)e∈E(G),定义e=uv的度d(e)=d(u)+d(v),其中d(u)和d(v)分别为u和v的度。本文的主要结果是:设G是n≥3阶几乎无桥的简单连通图,且G≠K_(1(?)n-1),G不含C_3和C_4,若对任何三个相互点不交的边e_0,e_1和e_2,d(e_0)+d(e_1)+d(e_2)≥n+7,则G有一个D-闭迹,从而G的线图L(G)是哈密顿图。     

图的控制圈的一个下界

引进控制圈的定义,同时讨论了一类2-连通图的控制圈的一个下界,若G是2-连通的非 Hamilton图,含有控制圈C,令R=V(G)-V(C),如果存在v∈V(C),使dR(V)≧2,则G包含的控制圈的长至少为2σ-2.     

一类泛圈图

本文证明了如果G是2连通无爪图,G不是圈,n=|v(G)|>q,G的每个导出子图A都满足φ(a_1,a_2),且G中不存在W′作为其导出子图,则G是泛圈图。     

三次图的收缩及其迭线图的分类

设图G为含有三角形或四边形的三次图,G_△为G的二角形收缩;G_□为G的四边形收缩。本文用计算机辅助证明了,若L(G)是2类的,则L(G_□)是2类的,若L~2(G)为2类的,则L~2(G_△)或L~2(G_□)为2类的。