共查询到18条相似文献,搜索用时 62 毫秒
1.
2.
定义1设图G为含有 p个顶点的标定图 ,对其进行x———正常染色的方法数是x的一个函数 ,可表示成x的一个多项式 ,称为图G的色多项式 ,记为f(G ,x)。引理1给定图G ,设u、v∈V(G) ,e=(u ,v)∈E(G)则f(G ,x)=f(G -e ,x) -f(Goe ,x)引理2设G是含q条边k个分图的 p阶图 ,则①f(G ,x)是p次多项式 ;②f(G ,x)中xp的系数为1;③f(G ,x)xp -1的系数为 - q;④f(G ,x)中常数项为0;⑤f(G,x)=∏f(Gi,x) ,式中Gi 是G的第i个分图 ;⑥f(G,x)中 ,系… 相似文献
3.
4.
唐明元 《上海师范大学学报(自然科学版)》2001,30(1):17-22
设Pr和Ps分别是两条具有r和s个顶点的路,用K3连接Pr和Ps的两个起点所得到的图,记作H(r,s)。h(G,x)是图G的伴随多项式。作者证明了,如果Pr-1,Ps-1和H(r,s)是不可约的,并且r和s是偶数(r,s≥4)。则H(r,s)的补图是色唯一的。同时还给出了计算伴随多项式的基本公式。 相似文献
5.
几类G=(p,p+1)且R(G)=—2图簇的补图的色性 总被引:3,自引:0,他引:3
江蓉 《青海师范大学学报(自然科学版)》1999,(3):8-14
本文利用图G的伴随多项式的最小根的性质,讨论了几类n个点n+1条边且R(G)=-2不可约图的补图的色性。 相似文献
6.
7.
当n是奇数时,Wn^*表示n阶轮相间地去掉(n—1)/2条幅所得到的图,利用图的色多项式等价性的关系,证明了W9^*是色唯一的. 相似文献
8.
鲍学文 《青海师范大学学报(自然科学版)》1992,(1)
本文给出多项式f(λ)=(λ-i)(λ-j)[λ(λ-1)…(λq)],1≤i≤j≤是 q T-多项式的一个充分必要条件,并给出f(λ)=λ(λ-1)~(n_1)(λ-2)~(n_2)…(λ-q)~(n_q)是 T-多项式的一个必要条件,其中 q≥4.n_1,n_2,…,n_q 是正整数. 相似文献
9.
图的伴随多项式 总被引:28,自引:7,他引:28
刘儒英 《青海师范大学学报(自然科学版)》1990,(3):1-9
本文系统地论证了图的伴随多项式的基本性质,并给出两个递推公式,也讨论了某些图的伴随唯一性. 相似文献
10.
11.
利用图标的方法得到图的全色数的一个上界,并证明其是可达的。其次给出图的强色数的一个上界,并对极图予以刻划,最后对图与补图的点荫度之间的关系给出一个简单的证明。 相似文献
12.
王涛 《山东大学学报(理学版)》1990,(4)
本文推广了图的 V_-多项式的概念及理论。这种广义图函数不仅与图有关,还与图的某一顶点子集有关,从而反映了图的更多的信息。讨论了广义 V_-多项式的基本定理,可乘性、拓扑不变性的充要条件以及广义二元色多项式及其应用。 相似文献
13.
14.
15.
16.
关于图的伴随多项式的几个结果 总被引:7,自引:4,他引:7
刘儒英 《青海师范大学学报(自然科学版)》1992,(1)
本文给出了图的伴随多项式的一个新的递推公式,并证明了:如果 P_m 是不可约路,则 m 1是一个素数.我们也讨论了伴随多项式的系数的某些性质。 相似文献
17.
研究图的带宽的上界与下界.通过引进记号N~(r)(S)和δ(S),改进了Harper的层次宽度下界以及Chvatal的层次深度下界.另外,本文还得到一个新的带宽上界,进而推广了Chvatal的另一结果. 相似文献
18.