二连通图的最长圈

本文证明:设G为n阶2连通图,D(x)={y|y∈V(G),d(x,y)≤2},d_d~*(x)表示D(x)中所有的点的度排成的非减度序列:d_1~*,d_2~*,…,d_j~*,d_(j+1)~*,…,d_(|D(x)|)~*中当下标j=d(x)时的度。δ_0=min{d(x)|x∈V(G)},D(δ_(i-1))={x|x∈V(G),d(x)≥δ(i-1)}(i=1,2,…,k),δ_i=min{d_(d(x))~*|x∈D(δ(i-1))}(i=1,2,…,k)且δ_0<δ_1<δ_2<…<δ_(k-1)≤δ_k,则C(G)≥min{n,2δ_k}。此外也给出δ_k的算法。     

关于有向图的强弧连通度

在图论中,图的连通性研究是一个较重要的方面,因为图的许多性质都与图的连通性有着密切的联系.李慰萱在其所著的《图论》一书中介绍了有向图的各种连通度,并且给出了有关强弧连通度λ_3与最小出入度δ_3的两个结论1.对任何有向图D,K_3≤λ_3≤δ_3.2.若D是一个强有向图,δ_3≥[p/2],则λ_3=δ_3.我们推广了上述第2个结论,得到了下面的结果:定理 若D是一个有P个顶点的有向图,记d_3(v)=min{odv,idv},如果存在整数k(1≤k≤4),使对D中任意k个顶点v_1,…,v_k都有d_3(v_1)+…+d_3(v_k)≥k/2(p-2)+1/2则λ_3=δ_3.     

关于恰有一个圈的连通简单图的图序列

本文证明了只有一个圈的连通简单图的图序列的充要条件。设 G 是一个图,它有 n 个顶点 a_1,a_2,…,a.d(a_i)表示在 G 中与 a_i关联的边数。序列d(a_1),d(a_2),…,d(a(?))称为 G 的度序列。如果 G 为一简单图,那么它的度序列称为图序列。     

关于S.Win的一个猜想

令G是一个图,P=|V(G)|,(?)u,v∈V(G),uv(?)E(G),d(u)+d(v)≥P+K,其中k是整数,则称G为Ore k—型图。S.Win提出如下猜想:若G是2n(n≥1)阶Ore k—型图(-1≤k≤2n-4),则G具有k+2个边不重的1—因子。本文证明了k=-1时,Win猜想成立。实际上,除个别图处,我们证明了更强的结论:若G是2n(n≥2)阶Ore-1—型图,且G(?)H_i(i=1,2),则G具有两个边不重的1—因子。     

关于竞赛图的弧k-反回路性质

设T=(▽,A)是一个竞賽图.|▽|=p称T具有P_k(p′_k)性质,若 xy∈A,T中存在一条长度为k-1的y-x路(x-y路),其中2≤k相似文献   

图的点可区别无圈边色数的一个上界(英文)

图G的一个正常边染色f,若满足:1)G中无2-色圈;2)对于V(G)中的任意两点u和v,有C(u)≠C(v),这里C(u)={f(uw)|uw∈E(G)},则f叫做图G的一个点可区别无圈边染色.图G的点可区别无圈边色数,记为χ′_(vda)(G),是图G的一个点可区别无圈边染色所用色的最小数目.证明了若图G是一个最小度不小于5,且顶点数不超过30Δ~4的图时,χ′_(vda)(G)≤10Δ~2,其中Δ是图G的最大度.     

一些循环图的同构因子分解

图的因子分解是图论中近年来十分活跃而且十分困难的一个课题。1983年著名图论学家A1spach教授在新加坡召开的图论学术会议上提出了“对所有循环图可分条件意味着存在一个同构因子分解”的猜想!本文就其猜想证明了以下结论:1.具有n个顶点的2K度连通循环图G,若t|n,则t|G;2.具有n个顶点的R度连通循环图G,若t|n/2,则t|G;3.G是三度或四度循环图,若t||E(G|,则t|G。     

关于图存在三角形的一个充分条件

对图论中的Woodall关于结合数的一个猜想作了研究.证明若图G的结合数bind(G)≥6 √22/7,则图G包含三角形,同时还证明了:若bind(G)≥3/2,且δ(G)＞P(G),则Woodall猜想是正确的,从而改进了现有的某些结果.     

图与补图的符号圈控制数

设γs′c(G)表示一个图G的符号圈控制数,G表示图G的补图,该文证明了:对任意n阶图G,均有γs′c(G) γs′c(G)≥(n-1)(n-8)/2,讨论了几类直和图的符号圈控制数,并提出了若干问题和猜想.     

使图的次序列是潜在Hamilton的一个充分条件

给定一个成图序列π,称π为潜在哈密尔顿的,如果存在一个图G,G以π为次序列且G是哈密尔顿的。本文证明了: 设图G的次序列满足下列条件: P_1=…=p_r=r<(p/2),p_(r 1)=…p_1=P(-r-1), P(-r)≤p_(t 1)≤…≤p_p,更有存在u与w∈V,d_(Gu)≥p-r-1, d_(Gw)≥p(-r),使UW∈E, (※)则G是哈密尔顿的,就是说,G的次序列是潜在哈密尔顿的。     

Ulam在重构猜想的一些讨论

Ulam重构猜想是图论中一个至今还没有得到根本解决的著名难题。本文首先建立了图的度序列的一种新的表达方法(§1)。然后在这种新表达方法的基础之上,得到了相容的三个必要条件(§2)。引入了几个新概念,得到了证明Ulam猜想成立或否定其正确性的一个新标准(§3),证明了当母图度序列为{M_i)}_(i=1)~n{a(i0)-di}_(i=1)~n时,Ulam猜思正确的结论,最后作为两个特殊情况,得到了当派生母图是欧拉图或正则图时,Ulam猜想亦正确的结论(§4)。     

三角化图的团划分数

在本文,我们证明了下述结果:(1)如果G=(V,E)是72个顶点的三角化图,则K(G)=α(G)≤cc(G)≤cp(G),cc(G)≤n-1,其中图G顶点独立数为α(G),它可在O(|V|+|E|)时间内求出;(2)如果G=(V,E)是n个顶点的特殊三角化图,V=S∪K,具有度序列为n-1≥d_1≥d_2≥…≥d_n,若对于S中任意顶点对x_i,x_j有|Adj(x_i)∩Adj(x_i)|≤1,则α(G)≤cp(G)≤α(G)+δ,其中,m=w(G)是图G的最大团的顶点个数。     

关于蕴含Ramsey数r_(pot)(K_n-ke,K_t-qe)问题

对于一个非增的非负整数序列π=(d_1,d_2,,…,d_n),如果π是某个n阶简单图G的度序列,则称π是可图序列,并称G是π的一个实现.给定一个图G,可图序列π称为是蕴含G可图的,如果π有一个实现包含G作为子图.对于2个简单图G_1和G_2,存在一个最小的正整数k,使得对于任何k项可图序列π,都满足π是蕴含G_1可图的或者π的补序列π是蕴含G_2可图的,正整数k记为r_(pot)(G_1,G_2),称为是G_1和G_2的蕴含Ramsey数.Busch等[3]给出了r_(pot)(G,K_t)的一个下界,并确定了当n≥t≥3时,r_(pot)(K_n,K_t)的值.笔者进一步给出了r_(pot)(G,K_t-qe)的一个下界,并确定了当n≥t≥4时,r_(pot)(Kn,K_t-e)之值,其中K_t-qe表示从t阶完全图K_t中去掉q条独立边后所得到的图.     

关于路与完全图的蕴含Ramsey数

对于一个n项非增的非负整数序列π=(d_1,…,d_n),若其是某个n阶简单图G的度序列,则称π是可图序列,并称G是π的一个实现.给定一个图H,如果π的某个实现包含H作为子图,则称π是蕴含H可图的.给出了当2≤n≤5,t≥2时r_(pot)(P_n,K_t)的确切值,从而完整确定了r_(pot)(P_n,K_t)值.     

具有固定顶点的树的代数连通度

设G是一个n阶简单连通图,图G的邻接矩阵记为A(G),令D(G)是G的顶点度对角矩阵,定义G的拉普拉斯矩阵L(G)=D(G)—A(G),设L(G)的特征值为λ_1≥λ_2≥…≥λ_(n-1)≥λ_n=0.在本文中,采用移接变形方法,讨论了树的代数连通度和直径之间的关系,获得了下面的结论:当树的顶点数固定时,树的代数连通度随着树的直径的增加而减少.进一步地,利用Cauchy-Schwarz不等式,讨论了树的代数连通度的界.     

三圈图的距离矩阵Inertia

令G是一个点集为V (G)={v_1,v_2,…,v_n}的连通简单图,让d_(ij)=d_G (v_i,v_j)]是图G中点vi和点vj之间的距离,图G的距离矩阵是D(G)=(d_(ij))_(n×n).用n_+(G),n_0(G),n_-(G)分别表示D(G)的所有特征值中正数、零、负数的个数。由此定义D(G)的Inertia为(n_+(G),n_0(G),n_-(G)),并且给出了围长为3的三圈图的距离矩阵的Inertia.     

关于强边着色猜想的最优图问题

著名图论专家Erd(o)s和Ne(s)et(r)il对图的强边着色数上界提出了一个猜想:当△为偶数时,x's(G)≤5/4△2;当△为奇数时,x's(G)≤1/4(5△2-2△+1),他们给出了当△=4的时的最优图.此处构造了一族图,并以此证明了当△为偶数时,如果Erd(o)s和Ne(s)et(r)il提出的强边着色猜想成立,则猜想中的上界是最优的.     

平方根图

设G是一个简单图及顶点为u1，u2，…，uv，d(vi)是点vi的度，令^～d(G)={[d(u1)]的平方根，[d(u2)]的平方根，…，[d(uv)]的平方根}，称G是一个平方根图，如果^～d(G)是G的邻接矩阵的一个特征向量，猜想：一个连通图G是一个平方根图的充分必要条件是G是一个正则图或半正则图，这个猜想在本文中得到了证明。     

2_补树图

若简单连通图G=(V,E)满足G=T_1UT_2,E(T_1)∩E(T_2)=φ,其中T_1和T_2是G的生成树,则G称为简单2—补树图.本文研究了简单2—补树图的若干性质(10个定理),其中包括:2—补树图G顶点度的性质,κ(G),λ(G),δ(G),△(G),2—补树图的构造性质和判定条件.     

只有两对顶点的度分别相等的图序列

只有两对顶点的度分别相等的图序列称为G(2,2)图序列.以Erdǒs-Gallai定理为基础,采用分段的方法讨论了G(2,2)图序列,得到非负整数不增序列d＝(d1,d2,…,dn)为G(2,2)图序列的充要条件.