一类(n,n+2)-图关于两种拓扑指标的排序

Hosoya指标和Merrifield-Simmons指标是化学图论中2个重要的拓扑指标。研究了一类(n,n+2)-图Tk的Hosoya指标和Merrifield-Simmons指标,根据Cm上2个接点u和v之间的距离,给出了该类图关于这两种拓扑指标的排序。

一类(n,n+2)-图关于Merrifield-Simmons指标和Hosoya指标的排序

Merrifield-Simmons指标和Hosoya指标是化学图论中两个重要的拓扑指标.图G的Merrifield-Simmons指标表示该图中所有独立集的数目,图G的Hosoya指标表示该图中所有匹配的数目.文中研究了一类(n,n+2)图T(k)的Merrifield-Simmons指标和Hosoya指标,并给出了该图类关于这两种拓扑指标的排序.

s不超过6的无标号(n,n/2+s)-奇图的计数

一个图称为(n,m)-图,若|V(G)|=n且|E(G)|=m.一个奇图是指每个点的度都是奇数的图.给出了一种新的图同构的定义,计算并给出了不同构无标号(n,n/2+5)-奇图的结果,并对s=4,6给出了不同构无标号(n,n/2+s)-奇图的完整结果.

Hamiltonian[k,k+1]-因子(英文)

本文考虑n/2-临界图中Hamiltonian[k,k+1]-因子的存在性。Hamiltonian[k,k+1]-因子是指包含Hamiltonian圈的[k,k+1]-因子;给定阶数为n的简单图G,若δ(G)≥n/2而δ(G\e)<n/2(对任意的e∈E(G)),则称G为n/2-临界图。设k为大于等于2的整数,G为n/2-临界图(其中n≥4k-6且n≥7),我们证明了对于G的任何Hamiltonian圈C,G中必存在包含C的[k,k+1]-因子。该结果改进了现有的一些有关Hamiltonian[k,k+1]-因子存在性的结果。

(2n+1)-可收缩图和2n-对可收缩图

令G是一个简单连通图.设S■V(G)且|S|=2n+1,将S收缩为一个顶点后所得到的图记α_((2n+1))(G,S).若G有完美匹配,且对于V(G)的任意一个有2n+1个顶点的子集S,图α_((2n+1))(G,S)有完美匹配,则称G是一个(2n+1)-可收缩图.设S_1,S_2,…,S_(2n)是V(G)的两两不相交的子集且|S_1|=|S_2|=…=|S_(2n)|=2,将S_i (i=1,2,…,2n)分别收缩为一点所得到的图记β_(2n)(G,S_1,S_2,…,S_(2n)).若G有完美匹配,且对于V(G)的任意2n个两两不相交的子集S_1,S_2,…,S_(2n),这里|S_1|=|S_2|=…=|S_(2n)|=2,图β_(2n)(G,S_1,S_2,…,S_(2n))有完美匹配,则称G是一个2n-对可收缩图.本文得到了(2n+1)-可收缩图和2n-对可收缩图的充要条件,并讨论了2n-临界图,(2n+1)-可收缩图,2n-对可收缩图及n-可扩图间的关系.

完全扩容图的点圈扩张性

一个连通的、N2-局部连通的无爪图是哈密顿图的一个充分条件,而新图类完全扩容图是无爪图.讨论了连通的、N2-局部连通图的完全扩容图的哈密顿性,利用归纳法证明了连通的、N2-局部连通且最小度至少是3的图的完全扩容图是哈密顿图.

EXISTENCE OF HAMILTONIAN k-FACTOR

A Hamiltonian k-factor is a k-factor containing aHamiltonian cycle.An n/2-critical graph G is a simple graph of order n which satisfies δ(G)≥n/2 and δ(G-e)<n/2 for any edge e∈E(G).Let k≥2 be an integer and G be an n/2-critical graph of even order n≥8k-14.It is shown in this paper that for any given Hamiltonian cycle C except that G-C consists of two components of odd orders when k is odd,G has a k-factor containing C.