当前位置: 首页 > >

蛛网图的邻点可区别的全染色_论文

发布时间:

第4 1 卷 第 2期  2 0 1 5 年 4月  兰 州 理 工 大 学 学 报  v0 L   4 1  No . 2   Ap r . 2 0 1 5   J o u r n a l   o f   L a n z h o u   Un i v e r s i t y   o f   Te c h n o l o g y   文章编号 :1 6 7 3 — 5 1 9 6 ( 2 0 1 5 ) 0 2 - 0 1 7 0 - 0 3   蛛 网图的邻 点可区别 的全染色  张东翰 , 李 超  ( 商洛学院 数学 与计算机应 用学院 , 陕西 商洛  7 2 6 0 0 0 )   摘要 :通过 穷举法和组合 分析法研究蛛 网图的邻点可 区别 的全染 色, 结果表 明蛛 网图的邻点可 区别 的全色数是存  在 的.   关键词 :蛛 网图} 邻 点可 区别 的全染色 ;邻点可 区别 的金色数  中图分类号 :O1 5 7 . 5   文献标 识码 : A  Ad j   a c e n t   v e r t e x   d i s t i n g u i s h i n g   t o t a l   c o l o r i n g   o f   s p i d e r   w e b   g r a p h   Z HANG  Do n g - h a n,LI   Ch a o   ( Co l l e g e   o f   Ma t h e ma t i c s   a n d   Comp u t e r   App l i c a t i on s ,Sh a n g Lu o   Un i v e r s i t y,S h a n g l u o ,7 2 6 0 0 0   Ch i n a )   Ab s t r a c t : Th e   a d j a c e n t   v e r t e x   d i s t i n g u i s h i n g   t o t a l   c o l o r i n g   o f   s p i d e r   we b   g r a p h   i s   s t u d i e d   b y   me a n s   o f   e x -   h a u s t i o n   me t h o d   a n d   c o mb i n a t i o n   a n a l y s i s   me t h o d .Th e   r e s u l t s   s h o w   t h a t   t h e   a d j   a c e n t   v e r t e x   d i s t i n g u i s —   h i n g   t o t a l   c h r o ma t i c   n u mb e r   o f   s p i d e r   we b   g r a p h   e x i s t s .   Ke y   wo r d s :s p i d e r   we b   g r a p h ;a d j a c e n t   v e r t e x   d i s t i n g u i s h i n g   t o t a l   c o l o r i n g ;a d j a c e n t   v e r t e x   d i s t i n g u i s —   h i n g   t o t a l   c h r o ma t i c   n u mb e r   图的染色是 图论 中最著名 和最 古老 的问题 之  由于其应用 的广泛性使得越来越多 的人对其进  行研究, 2 0 0 4 年, 张忠辅和陈祥恩等[ 1 ] 提 出图的邻  一 则称 厂是图 G的一个正常全染色 ( 简记作  P T C ) ,   , 且称数 X T ( G ) =mi n { k     I k - P T C ) 为 G的全色数.   如果  是 一个 k正 常全染 色 , 并 且 满足 :   3 )对任 意的 甜 , v EV( G) , 玑, ∈E( G) , 有 C(   ) ≠  C (  , 也就是 C(  ) ≠C ( 口 ) , 其 中 C( “ ) 一(  (   ) ) U   点 可 区别 的全 染 色 这 一 概 念 并 得 到 一 些 重 要 的 结  果, 随后 许 多 人 对 此 进 行 研 究 并 得 到 一 些 好 的 结  果[ 2   ] . 蛛网图是一个重要 的网络*私峁 , 研 究它  的染色对于网络权的分配和通信网络的设计有重要  的指导作用 , 通过对参考文献的研读 , 研究蛛网图的  邻 点可 区别 的全染 色.   { f ( u v ) l 鲫∈E ( G ) ) , C (   ) =C —C (   ) , 则称 . 厂 为图 G   的一个邻点可区别的全染色, ( 简记为 k - A V D T C) , 并  将  ( G ) =mi n { kl G有 一个 k - A V D T C) 称 为 图 G 的  邻点 可区别 的全色数.   定义 2 [ 6 ]   蛛形 图 S  的头 点 为 。 , 从 V 0出发  1 预备知识  定义 I   E   设G ( V, E ) 是简单 图, k 是 自然数 , 厂   是从  ( G ) UE( G) 到 C一 { 1 , 2 , …, k ) 的 映射 , 如果  满足:   有志 ( 志 ≥3 ) 条路 , 除" u o 外, 每条路有 k 个点 , 共有  (   一忌 。 +1 ) 个点, 删去 V o后 , 这 k条 路 分 别 记 为  P    ̄ " - T d  7



友情链接: