共查询到20条相似文献,搜索用时 0 毫秒
1.
设G=(V,E)是p阶简单无向图。 若G是2边连通的,设v∈V,若G-v不是2边连通的,则称点,是G的临界点。若G的每一点都是临界点,则称G是临界2边连通图 相似文献
2.
设G是临界h连通的非完全图,Hamidoune(Discrete Mathematics,32(1980),257—262)证明G中至少有2个度不大于3/2h-1的顶点,最近余景礼、马昱(华中工学院学报,1984,1)将结果改进为G中至少有δ(G)-h 2个度不大于3/2h-1的顶点,对已知的h与δ(G),上述的结果不是最好的,当h与δ(G)已知时,本文得到了G中度不大于3/2h-1的顶点数的最好下界,我们证明了如下定理。 定理1 设G是临界h连通的非完全图,则G中至少有2(δ(G)-h 1)个度不大于 相似文献
3.
D. R. Lick(J. Reine Angew. Math., 1972)首先证明:极小n棱连通图的最小度点数为n。W。Mader(Math。Ann。,1971)推广了上述结论,证明:极小n棱连通图至少有n 1个度n的点。本文推广了Mader的定理,证明了: 相似文献
4.
一、引言 我们讨论的图均为简单图,K和α分别表示图的连通度和独立数。我们采用文献[1]的术语和符号,并记G_n~k={G丨G为n阶k-连通图},H_e={G丨G是Hamilton连通图},用P_H(u,v)表示从u到v的Hamilton路。图G中的路P称为控制路,如果G[P(G)\V(P)]均为孤立点.给出图G中的一条(x,y)-路P,总认为是从x到y定向,表示的反向。若u,v∈V(P),则uv表示P上沿从u到v的路。又u≠y,v≠x,则u~+和v~-分 相似文献
5.
令G是一个n阶图.设C是G中的一个圈,如果G-V(C)是空图,那么称C是控制圈.令δ,κ和α分别表示图G的最小度、连通度和独立数.用σk表示G中任意k个独立点的度和的最小值.Bauer等人[1]证明了:设G是n阶2连通图.若σ3≥n κ,则G是Hamilton图.本文证明了:定理 设G是n阶3连通图.若σ4≥n 2κ,则G包含一个最长圈C,使得C是一个控制圈.界n 2κ是最好可能的.我们能构造一类图,它们满足定理假设,但不是Hamilton的.根据定理,我们有如下结论:推论1 设G是n阶3连通图.若σ4≥n 2κ并且δ≥α,则G是Hami… 相似文献
6.
7.
B. Jackson(参见J. Comb. Theory(B),29(1980),27—46)证明了2连通k正则的图G=(V,E),当点数n≤3k时G有Hamilton圈;在“The improvcment of Jackson's result on Hamiltonian Cyclesin 2-connected regular graphs”一文中我们改进了Jackson的结果,证明了2连通的k正则图,当 相似文献
8.
本文所涉及的图都是有限无向简单图。设G是一个图,总用V(G)、E(G)、c(G)分别表示G的顶点集、边集、周长,而令p=|V(G)|。设U(?)(G),总用G[U]表示G中由U导出的子图。如果对于任意U(?)V(G),总有G[U](?)K_(1,3),则称G为无爪图。设λ=min{d(u)+d(v)|u,v∈V(G),uv(?)E(G)},δ=min{d(u)|u∈V(G)},其 相似文献
9.
10.
一个图称作无爪图,如果它不含同构于K_(1,3)的导出子图。很重要的一类图——线图就是无爪的。目前已有的结果表明:相对于一般图而言,无爪图具有较好的性质。 关于无爪图的Hamilton性质,近年来 相似文献
11.
12.
本文讨论的图都是无向的简单图。图G称为无爪的,如果G没有同构于K_(1,3)的顶点导出子图。 关于2连通正则图的Hamilton性,1980年B.Jackson证明了:若G是2连通、k正则图,且G的顶点数不大于3k,则G是 相似文献
13.
对两条直角路线P和Q,总假定P中任一直线段与Q中任一直线段或者不相交,或者有唯一交点且该点不是任一直线段的端点,记P和Q的交点数为I(P,Q),对正整数m、n,定义I(m,n)=max{I(P,Q):|P|=m,|Q|=n},显然有I(m,n)=I(n,m)。 最近Teo和Tuan在文献[1,2]基础 相似文献
14.
4度1-正则图的一点注记 总被引:1,自引:0,他引:1
一个图叫做1-正则的,如果它的自同构群在它的弧集上作用正则,给出了4度1-正则循环图的分类,并且给出了n阶4度1-正则循环图的同构类的个数。 相似文献
15.
给定简单图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)的无序顶点 相似文献
16.
3连通图G中的边e称为可去的,若G-e是一个3连通图的剖分,讨论了3连通图中圈上可去边的分布,得到这些可去边数依赖于图中极大半轮数的下界,这些下界在某种意义上是不能改进的。 相似文献
17.
本文所涉及的图都是有限无向简单图。设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路 相似文献
18.
全着色边临界图的全色数 总被引:2,自引:0,他引:2
定义 对于简单图G(V,F),(?)e∈E(G),当 χ_T(G)>△(G)+1, χ_T(G-e)=△(G-e)+1时,则称G为全着色边临界图.其中厶(G)表示G的最大度,χ_T(G)表示G的全色数。 引理1 对图G(V,E)。(?)e∈E(G),若△(G)≥2,则 χ_T(G-e)≤χ_T(G)≤χ_T(G-e)+1。 定理1 若图G(V,E)是全着色边临界图,则 χ_T(G)=△(G)+2。 相似文献
19.
根据组合律,一元n+k(n=1,k≥3)相多体系中可能的不同无变度、单变度组合的数目分别由以下二式计算: 相似文献
20.
圈长唯一的最大图的边数 总被引:4,自引:0,他引:4
Erds于1975年提出了下列问题:设f(n)是有n个顶点的任何两个圈的长均不相等的图的最大可能的边数。试确定f(n)。 含有f(n)条边、没有两个等长圈的n个顶点的图称为圈长唯一的最大图。 相似文献