共查询到20条相似文献,搜索用时 15 毫秒
1.
设 G=(V,E) 为简单图,图 G 的每个至少有两个顶点的极大完全子图称为 G 的一个团. 一个顶点子集 S\subseteq V 称为图 G 的团横贯集, 如果 S 与 G 的所有团都相交,即对于 G 的任意的团 C 有 S\cap{V(C)}\neq\emptyset. 图 G 的团横贯数是图 G 的最小团横贯集所含顶点的数目,记为~${\large\tau}_{C}(G)$. 证明了棱柱图的补图(除5-圈外)、非奇圈的圆弧区间图和 Hex-连接图这三类无爪图的团横贯数不超过其阶数的一半. 相似文献
2.
3.
4.
陈学刚 《应用数学与计算数学学报》2005,19(2):85-88
图G的绑定数b(G)是指边集合的最少边数,当这个边集合从G中去掉后所 得图的控制数大于G的控制数. Fischermann等人在[3]中给出了两个猜想: (1)如果 G是一个连通的平面图且围长g(G)≥4,则b(G)≤5;(2)如果G是一个连通的平面图且 围长g(G)≥5,则b(G)≤4.设n3表示度为3的顶点个数,r4和r5分别表示长为4和 5的圈的个数.本文,我们证明了如果r4<(5n3)/2 10,则猜想1成立;如果r5<12,则猜 想2成立. 相似文献
5.
1000多年前, 英国著名学者Alcuin曾提出过一个古老的渡河问题, 即狼、羊和卷心菜的渡河问题. 最近, Prisner和Csorba等考虑了一般``冲突图"上的渡河问题. 将这一问题推广到超图$H=(V,\mathcal{E})$\,上, 考虑一类情况更一般的运输计划问题. 现在监管者 欲运输超图中的所有点\,(代表``items")\,渡河, 这里$V$的点子 形成超边 当且仅当这些点代表的``items"在无人监管的情况下不能留在一起. 超图$H$的Alcuin数是指超图$H$具有可行运输方案\,(即把$V$的点代表的``items" 全部运到河对岸)\,时船的最小容量. 给出了 $r$-一致完全二部超图和它的伴随超图, 以及$r$-一致超图的Alcuin数, 同时证明了判断$r$-一致超图是否为小船图是NP 困难的. 相似文献
6.
循环着色是普通着色的推广。本文中,我们研究了一类平面图的循环着色问题,并证明了这类平面图是循环色临界的,但不是普通色临界的,同时,我们还研究了循环着色与图G_k~d中的链之间的关系. 相似文献
9.
10.
11.
12.
设e是3连通图G的一边。如果G-e是某个3连通图的剖分,则称e是G的可去边。用v表示G的顶点数,本文证明了当v≥6时,3连通平面图G的可去边数的下界是v+4/2,此下界是可以达到的。 相似文献
13.
低度平面图的边面全色数 总被引:2,自引:0,他引:2
王维凡 《高校应用数学学报(A辑)》1993,(3):300-307
平面图G(V,E,F)的边面全色数X,(G)是使得集合E(G)∪ F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数。本文提出猜想:对任何平面图G,有△(G)≤X,(G)≤△(G)+3;并对顶点度不超过3或面度均为3的平面图证明了这个猜想为真。 相似文献
14.
平面图 G(V,E,F)的点面全色数 xs(G)是使得集合 V(G)U F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数.本文证明了:(1)若 G 为极大平面图,则4≤xs(G)≤6;且 xs(G)=4当且仅当 G 为点次模3-正则图.(2)若 G 为△(G)≤3的简单平面图,则 xs(G)≤6.一、引言本文限于考虑平面图 G(V,E,F),其中 V,E,F 分别为 G 的点集合,边集合和面集 相似文献
15.
简要介绍了图的关联着色问题的起源、发展情况及目前已有的结论,对一类特殊的图——极大外平面图(△≠6),给出了其关联色数. 相似文献
16.
如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数.证明了:若G是一个最大度△(G)≠5,6的平面图,则lc(G)≤2△(G). 相似文献
18.
可平面图完备色数唯一性问题赵克文(华南师范大学数学系,广州510631)我们已经知道,图的点色数、边色数,点边金色数X_T都是唯一的。那么,可平面图的边面完备色数X唯一吗 ̄[2]?本文对此有结论:并非每一可平面图的完备色数都唯一,由此就产生问题:X(... 相似文献
19.
循环着色是普通着色的推广.本文中,我们研究了一类平面图-“花图”的循环着色问题,证明了由2r 1个长为2n 1的圈构成的“辐路”长度为m的花图Fr,m,n的循环色数是2 1/(n-m/2),并证明了在这类图中去掉任何一个点或边后,循环色数都严格减少但普通色数不减少,即这类图是循环色临界的但不是普通色临界的.同时,我们还研究了循环着色与图Gkd中的链之间的关系,给出了两个等价的条件. 相似文献