图中K个边不交的圈的存在性问题

记h(k)是使得满足ε=ν+h(k)的有限的无向图G包含k个边不交的圈的最小整数,P.Erds和L.Pósa证明了h(2)=4且对于任意正整数k≥1,存在充分小的正常数c1和充分大的正常数c2,使得c1klog2k≤h(k)≤c2klog2k。现把充分大的正常数c2的界缩紧到2.1<c2≤3,特别当c2为整数时,则c2=3,并比较简洁地证明了h(3)≤10和当图G是平面图时,对于任意正整数k≥2,h(k)=4k-5。

边不交圈的图的符号差(英文)

一个有限简单图的符号差是指其邻接矩阵的符号差,即邻接矩阵的正惯性指数和负惯性指数的差.马海成等猜测一个图的符号差小于等于长度为4k+5圈的个数,大于等于长度为4k+3圈的个数的负值,本文证明了该猜测对边不交圈的图是成立的.

图的强彩虹连通数

如果图G的任意两个顶点由一条路P连接,其中路P的每一条边着不同的颜色,则称图G为彩虹连通图.对图G的任意两个顶点u和v,G的彩虹u-v测地线是一条长为d(u,v)的彩虹路,其中d(u,v)表示最短的u-v路的长度.图G称为强彩虹连通的如果对G的任意两点u和v间都存在一条彩虹u-v测地线.图G的强彩虹连通数是指使得图G是强彩虹连通而用的最少颜色的数目,用src(G)表示.该文首先给出了一个含边不交的k-圈图的一个强彩虹连通数的上界.接着给出了这个上界取等的充分条件.