共查询到20条相似文献,搜索用时 46 毫秒
2.
有关直积图的色数,在图论中有Hedetniemi猜想,该猜想是建立在连通图的基础上,并且已证明该猜想对于一些特殊图是成立的.证明了对于连通的点传递图,Hedetniemi猜想在分数染色意义下也是成立的. 相似文献
3.
将矩阵直积的概念引入图论,证明了直积图的结点数、度及特征值分别等于原图结点数之积、度之积和特征值之积,并将这些性质应用于由两个膨胀图构造一个新的膨胀图,分别从矩阵的角度和图的角度给出了构造算法。 相似文献
4.
5.
图G(V,E)的2-距离染色是指正常的顶点染色,且任意距离不大于2的两个顶点着不同的颜色.得到弱直积图的一个2-距离色数的可达界,即Δ(G).Δ(H)+1≤χ2(G×H)≤χ2(G).2χ(H),且给出一些特殊弱直积图的2-距离色数,说明此界可达.如χ2(P2×Pn)=Δ(P2).Δ(Pn)+1=3(n≥3),χ2(Pm×Pn)=Δ(Pm).Δ(Pn)+1=5(m≥3,n≥3)说明下界可达,χ2(Km×Kn)=χ2(Km).2χ(Kn)=mn,说明上界可达. 相似文献
6.
7.
8.
图G的无循环着色是指图G的顶点着色使得G的任何相邻的顶点不着双色且在图G没有双色圈.研究了Meredith图和系列平行图的无循环着色,证明了Δ(G)≥5的系列平行图的无循环色数a(G)≤Δ(G)+1. 相似文献
9.
10.
简国明 《佛山科学技术学院学报(自然科学版)》2009,27(4):1-2,6
在有关结论的基础上.应用数论方法给出Boesch和Tindell提出的“连通的循环图是Hamilton图”猜想的又一证明。 相似文献
11.
12.
13.
王迪吉 《新疆师范大学学报(自然科学版)》1998,(2)
设C(G,S)是有限群G上关于S(S(?)G)的Cayley有向图。给定G的一个子群H,我们在C(G,S)上引入商Cayley有向图的记号,它在某种意义上来说类似于群论中的商群,因此可在这一类图上讨论其性质。 对于g∈G,我们用N~ (g)表示g在C(G,S)中的外邻集。设集合K={g∈C|N~ (g)=S},可以看出它是G的子群,我们称其为C(G,S)的核。当H=K时,Cayley有向图与它的商有向图之间存在着一些非常好的同构关系。在这个假定下,我们进一步根据商有向图及核K为C(G,S)的自同构群刻划出了一系列特性。 相似文献
14.
15.
16.
17.
18.
群图的基本理论及置换群图的构造 总被引:2,自引:0,他引:2
建立了群图与可靠通信网之间的关系及群图构造的基本理论 ,在此基础上得到构造置换群图的两种实用方法——最小生成元法和轮换群图法 ,并应用这两种方法得出置换群可以生成任意 n节点和大于其最小连通度的连通群图的结论 相似文献
19.
李向东 《河北理工学院学报》1999,21(1):56-58
通过对三次图结构的研究给出了两个主要结论:(1)对连通度μ(G)=0,1,2,3,分别给出点数P=|V(G)|的可达到的下界;(2)2—连通图G,存在2—连通三次图G′,G′可收缩到G。 相似文献
20.
准补图的紧性和超紧性 总被引:2,自引:2,他引:0
张秀平 《北京师范大学学报(自然科学版)》1999,35(3):316-319
推广了补图的概念,找到了另一类紧图和紧超紧图,对于(m,k)圈的准补图是否为紧图或超紧图作了详尽的讨论。 相似文献