论文部分内容阅读
设图G=(V(G)，E(G))是简单图，其中V(G)和E(G)分别表示图G的顶点集和边集.令△(G）是图G的最大度. 给定非负整数r，s和t，图G=(V(G)，E(G))的[r,s，t]-染色指的是映射c:V(G)∪E(G)→{0，1,…，k-1}，使得图G中任意相邻的两个顶点vi，vj满足|c（vi）-c(vj)|≥r;任意两条相邻的边ei，ej满足|c(ei)-c(ej)|≥s;并且任意顶点vi和与其关联的边ej满足|c（vi）-c(ej)|≥t.使得图G存在[r，s，t]-染色的最小正整数k称为[r，s，t]-染色数，记作Xr，s，t(G).显然，[1，0，0]-染色是点染色，[0，1，0]-染色是边染色，[1，1，1]-染色是全染色.由于[r，s，t]-染色是点染色，边染色以及全染色的结合与推广，并且参数r，s，t之间的大小关系也很复杂.因此，[r s，t]-染色问题的研究有一定的难度.目前，[r，s，t]-染色的研究主要集中在两个方面:一是对某类图的[t，s，t]-染色进行研究;二是限定参数r，s，t的值对图G的[r，s，t]-染色进行研究.本文就轮图以及与轮图相关的几类图的[r s，t]-染色展开了研究: (1)确定了友谊图C(n)3的[r，s，t]-染色数的值和界. (2)讨论了当m为不小于3的奇数时，Jahangir图Jn,m的[r，s，t]-染色.首先给出了当min{r, s，t}=0时，Jahangir图Jn，m的[r，s，t]-染色数的值与界.当min{r, s，t}≥1时，分别给出了n为奇数时以及n为偶数时，Jn,m的[t，s，t]-染色数的值与上界. (3)研究了轮图Wn以及多轮图NWn的[r，s，t]-染色.首先证明了当min{r，s，t}=0时，以及当min{r，s，t}≥1且△(NW2n)≥6时，NW2n的[r，s，t]-染色数等于其生成友谊图C(Nn)3的h，s，t]-染色数.然后确定了当r≥1，s≥1，1≤t≤2s时，偶轮图W4的[r，s，t]-染色数的值与上界.最后给出了△（NW2n+1）≥5的多奇轮图NWn+1的[r，s，t]-染色数的值与界. (4)确定了扇图Fn以及多扇图NFn的[r，s，t]-染色数的值与界.首先给出了当min{r，s，t}=0时，扇图Fn以及多扇图NFn的[r，s，t]-染色数的值与界.其次证明了当min{r，s，t}=0时，以及当min{r，s，t}≥1，△(NF2n)≥6;和△（F2n）=4且s≥t，或s＜t≤2s与r＞s+t时，多偶扇图NF2n的[r，s，t]-染色数与其生成友谊图C(Nn)3的[r，s，t]-染色数相等.然后给出了1≤s＜t≤2s且1≤r＜s+t时，X r，s，t（F4）的上界.最后确定了当min{r, s，t}≥1时，多奇扇图NF2n+1的[r，s，t]-染色数的值与界.