图的联结数及其三角形

简单图G的联结数记作bind(G),它是满足下式的最大实数C。这里V(G)是图G的顶点集,N(u)表示图G中与顶点u相邻接所有顶点作成的集合。     

2连通正则无爪图中的Hamilton圈

本文讨论的图都是无向的简单图。图G称为无爪的,如果G没有同构于K_(1,3)的顶点导出子图。 关于2连通正则图的Hamilton性,1980年B.Jackson证明了:若G是2连通、k正则图,且G的顶点数不大于3k,则G是     

Hamilton图的一个充分条件

设G=G(V,E)为简单图。d(u)表G中顶点u的度,d(u,v)表顶点u与v的距离。ω(G)表G的分支个数。本文证明了下述定理。 定理 阶数n≥3的简单图G满足下述两条件:     

Ramsey数r(3,14)和r(3,15)的新下界

Ramsey数r(p,q)是满足下述条件的最小正整数r:对任意的r个顶点的图G(本文中的图均指无向简单图),则G或有P个顶点的团(即完全子图k_p)或有q个顶点的独立集。Ramsey 1930年证明了Ramsey数的存在性,Ramsey理论的研究在近六十年中也取得了许多有意义的结果(参看文献[2]     

哈密顿道路图

图G的哈密顿道路图H(G)是和G具有相同顶点集的图,并且其中任意两个顶点u和v是邻接的当且仅当G含有一条哈密顿u-v道路。本文呈现出哈密顿图同构于哈密顿道路图的特征。     

关于Alspach问题的解

本文研究Alspach提出的图的正交因子分解问题,给出了一个图有一类因子分解与任意对集正交的条件。 1 引言本文所考虑的图均指有限无向图,它不含重边和环。设G是一个图,分别用V(G)和E(G)表示图G的顶点集和边集,用d_G(x)表示顶点x在G中的次数。设g和f是定义在     

关于Benhocine、Clark等人的一个猜想

所讨论的图均指无向、有限的简单图。图G的生成闭迹或S-闭迹(S-circuit)是指一个闭迹使得它含有图G的所有的顶点。如果G中存在一条闭迹T使得G的每条边至少有一个顶点在T上,则称T是D-闭迹(Dominating circuit)。连通图G称为几乎无桥的如果它们的每一个桥至少关联一个次数为1     

图的生成环及线图的Hamilton性

所讨论的图都是无向的、有限的简单图。图G的一个生成环(S-circuit)指的是一条通过图G所有顶点的闭迹。一个连通图称为几乎无桥图,如果G的任一桥至少关联一个度为1的顶点。1977年,F.T.Boesch、C.Suffel和R.Tindell提出了有生成环图的     

几类由PLD确定的连通图

给定简单图G=(V,E),其中V是顶点集,E是边集。若对V的两个顶点u,v,在G中存在含有i个顶点的一条(u,v)路,则称性质P_i(u,v)成立。令S_i(2≤i≤n)是G中有性质P_i(u,v)的无序顶点     

连通、局部连通、无爪图是点泛圈图

本文只讨论有限、无向、无环和多重边的简单图。V(G)、E(G)分别表示图G的顶点集和边集。如果S(?)V(G),用G[S]表示子集S在G中的导出子图。若u∈V(G),N(u)表示u点的邻域,即邻接于u点的全体顶点的集合。     

由一类图的着色导出的素数子集的分类

设P表示全体素数的集合,D(?)P。令G(Z,D)表示这样一个图:它的顶点集是全体整数的集合,两个顶点x和y之间有边连结当且仅当|x—y}∈D。Eggleton,Erds和Skilton等在文献中证明了:不论对任何素数子集D(?)P,图G(Z,D)的色数至     

k-连通无爪图中的Hamilton路和Hamilton-连通性

本文涉及的图都是无向简单图。而无爪图就是不存在顶点的导出子图同构于K_(1,3)的图。 1985年,Matthews等讨论了无爪图中的最长路和最长圈。证明了:设G是一个n阶无爪图,其最小次δ≥1/3(n-2)。若G     

Ore-2型图中存在两个边不相重的Hamilton圈

本文讨论的图都是无向的简单图。设G是一个图,分别用V(G)和E(G)表示图G的顶点集和边集。又设“、v∈V(G),用d(v)表示v的次数,用vu表示连结u、v的边。     

k连通无爪图中最长的圈

本文所涉及的图都是有限无向简单图。设G是一个图,总用V(G)、E(G)分别表示G的顶点集、边集,而p=|V(G)|。设UN(G),总用G[U]表示G中由U导出的子图。图G称为无爪的,如果对于任意UV(G),总有G[U]K_(1.3)。图G称为m路     

关于简单MCD图的一个定理

设S_n是n个顶点的没有两个等长圈的简单图的集合。如果对于S_n中的一个图G,S_n中不存在适合|E(G′)|>|E(G)|的图G′,则称其为简单最大圈分布图,简称简单MCD图(ma-     

1坚韧图最长圈的新的充分条件

本文所涉及的图都是有限无向简单图。设G是一个图,用V(G),B和c(G)分别表示G的顶点集、边集和周长,d(u,v)表示u和v间的距离,且设p=|V(G)|。     

K_(1,3)-free图中的圈

本文说的是简单图。 设G是任一个n阶的图。如果G中有长为n的圈,则G是哈密顿图。如果对每个k,3≤k≤n,G含有长为k的圈,则说G是泛圈图。如果对G的每个顶点v,图G中都有长为k的圈经过顶点v,则说G是点k圈图。如果对每个k,3≤k≤n,G都是点k圈图,则说G是点泛圈图。     

关于路图P_3(G)的Hamilton性的两个结果

“路图”是线图概念的发展.给定一个图G及自然数k≥2,路图P_k(G)的顶点是G中k个顶点的路P_k;两条路P_k在路图中是相邻的,如果它们的并是P_(k+1)或C_k.为     

临界2棱连通图的最大度及度大于4的点数

设G是临界2棱连通图,D是G中2度顶点集合,D_(≥2k-1)(G)={x:(x∈G)∧(d(x)≥2k-1)},D_(2k-1):2k(G)={x:(x∈G)∧(2k-1≤d(x)≤2k)},其中k是自然数。[a]表示不大于a的最大整数。我们得到如下结果:     

关于A.Ainouche和N.Christofides的一个猜想

一、引言 Ainouche和Christofides提出一个猜想:设a,b为2-连通图G=(V,E)的两个不相邻顶点,若,有,则G是Hamilton图当且仅当G+ab是Hamilton图。