完全图的准强边着色图的计数

使用准强边着色矩阵讨论了完全图的准强边着色图的计数。

准强边着色图的分类

如果图G已有一个合理边着色,使得图G中所有相邻顶点间的关联边着色集合相互不同,则这种边着色称为图G的准强边着色。具有准强边着色的图称为准强边着色图,并对准强边着色图给出一个分类。

边着色图上最大弱适当树问题近似算法

边着色图上最大弱适当树问题是针对给定的边着色的简单无向图,寻找1个弱适当树,使得这颗树包含顶点的个数尽可能多,这一问题是NP-hard。利用弱适当树及边着色图的性质,通过限制着色边的颜色数为2,从算法理论的角度来考虑该问题,设计了最坏情况界为2的多项式时间近似算法,并给出近似算法的紧例及其分析。

边着色完全图中的单色圈和单色树

令f(r,n)是使得任意r-边着色完全图K_(n)包含一个长度至少为k的单色圈的最大正整数k.2009年,Faudree,Lesniak和Schiermeyer提出猜想:任意(r+1)-边着色完全图K_(n)包含一个长度至少为n/r的单色圈,其中r≥2.同时他们还证明了f(2,n)≥[2n/3]且界是紧的,其中n≥6.2011年,Fujita证明了当n=2r时猜想不成立,同时还证明了任意r-边着色完全图K_(n)包含一个长度至少为n/r的单色圈,其中1≤r≤n.本文中我们证明了存在(r+1)-边着色完全图K_(n)包含一个长度小于n/r的单色圈,其中n=tr+1,r≥2且n-1/r为正偶数.令c表示K_(n)的某种k-边着色.在边着色c的完全图K_(n)中,令moc(K_(n),c)表示单色树的最大阶数且moc(n,k)=min{moc(K_(n),c):c是K_(n)的某种k-边着色}.我们还证明了当n≡0,1(mod 4)时,moc(n,3)=[n/2];当n≡2,3(mod 4)时,moc(n,3)=[n+1/2],其中n≥3.

次模函数近似算法求最小颜色生成树(英文)

给定图G并对其进行边着色,G的最小颜色生成树(MCST)问题是指,找出G的一棵生成树,使得其边集所着颜色数最少.最小颜色生成数问题MCST已被证明是NP-、APX-完备的,从而此问题没有近似比为常数的近似算法.本文中,我们利用次模函数理论(贪婪算法的思想)给出最小颜色生成树问题的一个近似算法,且此算法的近似比为最好结果.

关于n-方体的2-虹连通(英文)

边着色图中的一条路称为虹当它的边着色各不相同.如果一个图的任意两点间存在k条内部不交的虹,则称该图为k-虹连通图.记rCk(G)为使图G为k-虹连通图的最小色数.本文考察了一类特殊图n-方体,在k=2时,有rC2(Qn)=max{4,n},n≥2.