共查询到16条相似文献，搜索用时 187 毫秒
1.
证明了:如果图G是不含3-面上有5-顶点和(4,6,6)-面的最大度为6的平面图,则它满足全着色猜想,即对图G有Δ(G)+1≤χT(G)≤Δ(G)+2. 相似文献
2.
如果图G有一个合理边着色,使得图G中任意两个相邻顶点间的关联边着色集合相互不同,则这种边着色称为图G的准强边着色.有一个准强边着色的图称为网络图(或准强边着色图).使图G有一个准强边着色的最小色数称为网络图(或准强边着色图)的准强边色数,它被记为χ′qs(G).讨论了网络图的分类问题和网络完全图的计数问题,提出并证明了下述网络图猜想(或准强边着色猜想):如果连通网络图有△(G)≥2,则网络图G的准强边色数有△(G)≤χ′qs(G)≤△(G)+3. 相似文献
3.
彩春丽谢德政 《西南大学学报(自然科学版)》2013,35(2):99-102
研究了平面图的线性着色.对平面图G,证明了lc(G)≤min{2Δ(G)+3,Δ(G)+15}和lc(G)≤max{└0.9Δ(G)┘+4,┌Δ(G)/2┐+22},改进了平面图线性着色色数的上界. 相似文献
4.
连广昌 《金陵科技学院学报》2006,22(4):1-7
如果图G已有一个合理边着色,使得图G中所有相邻顶点间的关联边着色集合相互不同,则这种边着色称为图G的准强边着色。具有准强边着色的图称为准强边着色图,并对准强边着色图给出一个分类。 相似文献
5.
如果图G有一个合理边着色,且图G中所有顶点上的关联边着色集合都互不相同,则这种合理边着色又称为图G的强边着色。具有强边着色的图称为图G的强边着色图。使图G有强边着色的最小色数称为图G的强边色数。本文利用强边着色矩阵,讨论了完全图的强边着色及其分类,证明了:当n是奇数时,图Kn是一个第二类强边着色图,且χs′(Kn)=Δ(Kn) 1;当n是偶数时,图Kn是一个第三类强边着色图,且χs′(Kn)=Δ(Kn) 2。或者,χs′(Kn)=3 2[(n-2)/2],这里[x]表示取小于、等于x的最大整数。 相似文献
6.
连广昌 《金陵科技学院学报》2005,21(4):1-5
如果图G有一个合理边上色,使图G的所有相邻顶点的关联边上色集合都互不相同,则称图G为准强边着色。本文证明了：△（G）≥2时,图G的准强边着色色数满足△（G）≤x′QS（G）≤△（G）＋2。 相似文献
7.
P_m×P_n和P_m×C_n的邻强边染色 总被引：3，自引：2，他引：3
设G是阶数不小于3的简单连通图,G的κ-正常边染色称为是邻强的,如果对G任意相邻两顶点关联边的颜色构成的颜色集合不同,则κ中最小者称为是G的邻强边色数。本文研究了Pm×Pn和Pm×Cn的邻强边色数。 相似文献
8.
徐光辉 《浙江农林大学学报》1998,15(3):304-309
设G 为n 阶简单图, n(G)为G 的最小特征值。本文证明了:若G 为n 阶单圈图, G＊ 为C3 的每个顶点分别与P k -1 , P k1-1 , P k2-1 的一个一度点相连而得的单圈图, 其中k k1 k 2 1 , k -k 2 1 , k +k 1 +k 2 = n , 则 n(G) n(G＊)等号成立当且仅当G≌G＊ 。 相似文献
9.
主要证明了一个群如果可以表示为3个或4个交换子群的并,则下列结论成立:(1)群G可以表示成3个交换子群的并当且仅当G/Z(G)≌Z_2×Z_2;(2)群G可以表示成4个交换子群的并当且仅当G/Z(G)≌S_3或G/Z(G)≌Z_3×Z_3. 相似文献
10.
余春刚 《金陵科技学院学报》2006,22(4):7-11
已知G2=G∪{uv dG(u,v)=2,u,v∈V(G)},如果定义算法,1)令G2=G0,2)Gk=Gk-1\{uv},dG(u,v)=2,这样就可以得到边数更少的图G。考虑G2推出3-NZF但∈τ1,3且|V(G)| |E(G)|的极小反例,以及Gτ1,3但G2不推出3-NZF且满足1.|E(G)|-|V(G)|尽可能小,2.在1)成立的条件下,|E(G)|尽可能小的反例,于是有结论:G2推出3-NZF,当且仅当Gτ1,3。 相似文献
11.
研究了没有4圈,5圈和共点三角形的平面图的结构,利用这个结构,证明了这类图是3-可染色的。它加强了Borodin、Sanders和Zhao证明的结果,并且又是对Steinberg猜想的一个支持。 相似文献
12.
13.
韩忠海 《山西农业大学学报(自然科学版)》2007,27(2):209-213
在S.Karimis和Dragan Stevanovic研究的基础上,研究并得出了(k,l)-正则极大平面图存在的必要条件。并对存在的(k,l)-正则极大平面图进行了构造。不仅彻底解决了S.Karimis提出的问题,而且就是否存在对应阶n>12的(k,l)-正则极大平面图研究和证明,并得出当阶n>13时仅存在(3,6)、(4,6)、(5,6)-正则极大平面图,同时给出了对应的(k,l)-正则极大平面图的一种构造方法。 相似文献
14.
韩忠海 《山西农业大学学报(自然科学版)》2008,28(1):106-108
当图的顶点数n>12时,不存在正则极大平面图。S.Karimi et.al.提出了(r,k)-正则极大平面图的概念,并讨论了(5,6)-正则极大平面图的存在性。作者曾讨论了阶n>12的(k,l)-正则极大平面图的存在条件及构造方法,研究并讨论了阶n(n>12)的(k,l)-正则极大平面图的存在性及其构造,对于剩余的两种情况,同时提出了两个猜想。本文在此基础上又证明了其中一个猜想的正确性——不存在12阶的(4,8)-正则极大平面图。 相似文献
15.
A near-optimum parallel planarization algorithm is presented. The planarization algorithm, which is designed to embed a graph on a plane, uses a large number of simple processing elements called neurons. The proposed system, composed of an N x N neural network array (where N is the number of vertices), not only generates a near-maximal planar subgraph from a nonplanar graph or a planar graph but also embeds the subgraph on a single plane within 0(1) time. The algorithm can be used in multiple-layer problems such as designing printed circuit boards and routing very-large-scale integration circuits. 相似文献
16.
Wiener指数是指一个连通图中所有顶点之间的距离之和．给定一个连通图G,若存在G中一棵子树T,使得w（G）=W（T）,则称T为G的一棵保Wiener指数的树．给出了对于满足下列条件下的某类m＋2k＋1阶联图PmVP2k＋1中均有保Wiener指数的子树：m=t2＋4t＋8/3k3-k2＋4/3k＋1（t≥k2-1/2k）此结果蕴含了先前的一个结论． 相似文献