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

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

求图的色多项式的一种新方法及其应用

设G是简单图,f(G,t)是它的色多项式,k是自然数,我们记 [t]_k=t(t—1)(t—2)…(t—k+1)。 定义1 若图G的生成子图H的每个分支都是完全图,则称H为G的理想子图。     

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

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

圈长唯一的最大图的边数

Erds于1975年提出了下列问题:设f(n)是有n个顶点的任何两个圈的长均不相等的图的最大可能的边数。试确定f(n)。 含有f(n)条边、没有两个等长圈的n个顶点的图称为圈长唯一的最大图。     

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

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

Riemann流形上Hardy-Littlewood极大算子的有界性

在本文中,D表示有向强连通图,D(n,s)表示连通有向循环图。 设C是V(D)的真子集,若D-C不为强连通的或者为单一顶点,则称C为D的点截集。用B(D)记D中点截集的全体。     

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

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

图的生成环及线图的Hamilton性

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

块中圈含弦的最大数目及其极图刻划

设C为简单图G的圈,我们称导出子图G[C]的不在C上的边为C的弦。本文证得:设G是2-连通图且|V(G)|≥2n+1,n≥3。若G的最小度δ(G)≥n,则G含一个圈,其弦数至少为n(n-2)+1,除非G是K_(n,m)(m>n)或Petersen图。从而Gupta,     

简单MCD图的边数的上界

用f(n)(f~*(n))表示具有n个顶点的没有两个等长圈的图(简单图)的最大可能的边数。确定f(n)的问题是Erd(?)s于1975年提出的至今尚未解决的难题。我们称具有n个顶点和f(n)(f~*(n))条边的图(简单图)为MCD图(简单MCD图)。在[2]中,我们已经证明f(n)     

1坚韧图的Hamilton性

设G是一个图,且t是一个实数,若对每个,其中k(G—S)是G—S的分支数,则称G是t坚韧图(t-tough graph)。显然,1坚韧图是2连通的。用δ,κ,α分别表示G的最小度、连通度和独立数,利用以上记号,有如下定理: 定理1 设G是p阶1坚韧图,若δ≥     

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

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

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

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

实Clifford分析中带共轭值的边值问题解的存在唯一性

给定连通开集,其边界Σ为光滑定向紧致Liapunov曲面;a(t)、b(t)、c(t)、d(f)、g(t),t∈Σ。寻求在Ω正则,在Ω+Σ连续的函数Φ(x)∈A_n(R),它适合     

每个4-正则简单图包含一个3-正则子图

1973年,C.Berge猜想:每个4-正则简单图包含一个3-正则子图,1979年,v.Chvátal,H.Fleischner,J.Shechan和C.Thomassen猜想:设G是奇阶4-正则图。若λ_c(G)∈{6,8},则G存在一点x,使得G—x有3-正则生成子图。(λ_c(G)是图G的边圈连通度)。本文以更一般的形式证明这两个猜想为真。 一个图G是强4-边连通的,若G是4边连通的,且对任一个基数为4的边割集5,G—S有平凡     

关于两类图的整和数

本文中的图均指无向简单图,以N,Z分别表示全体自然数及全体整数集合.对子集S(?)Z(N),S上的整和(和)图定义为图G=(S,E),满足条件对u,v∈S,uv∈E当且仅当u v∈s.此时,S称为G的一个整和(和)标号.一个图称为整和(和)图,如果它同构于某一子集S(?)Z(N)上的整和(和)图.容易验证,对一个有m条边的n阶图G,G∪mK_1是一个和图,只需标定G的顶点为2~i,1≤i≤n,同时对v_i,v_j∈E(G),标定对应的孤立点2~i 2~j即可.因此,对每一个图G,存在一个最小的非负整数r,使G∪rK_1为和图,记σ(G)=r,并称为G的和数.图的整和数ξ(G)类似定义,只是标号范围放宽到整数集上.容易看到ξ(G)≤σ(G).     

局部n(弧)强连通有向图

G.Chartrand等在1974年提出了局部u连通的概念。本文将此概念推广到有向图(若有向图D中每个点的邻接点集的导出子图是n(弧)强连通的,则称D为局部n(弧)强连通的),然后给出了下面的定理。 定理1 任何弱连通的而且局部n弧强连通的有向图是(n+1)弧强连通的。 定理2 任何弱连通的而且局部n强连通的有向图是(n+1)强连通的。 定理2是G.Chartrand等的一个定理的推广,     

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路     

几类由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)的无序顶点     

关于最大唯一圈图

P.Erd(o|¨)s于1975年提出了下列问题:设f(n)是有n个顶点的任何两个圈的长均不相等的图的最大可能的边数,试确定f(n)。十余年来,对这一问题的研究几乎没有进展。我们称Erd(o|¨)s问题中所描述的图为最大