资源描述：
《关于图一般邻点可区别全染色》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、系统科学与数学勺此材,,一关于图的一般邻点可区别全染色严谦泰安阳师范学院数学与统计学院,安阳摘要提出了一般邻点可区别全染色的新概念,给出了路、圈、星、树、二部图、轮、扇、完全图的一般邻点可区别全染色指标并据此提出猜想关键词一般邻点可区别边染色,一般邻点可区别全染色,一般邻点可区别全染色指标主题分类号引言随着图的染色间题在现实中被广泛应用,它逐渐成为众多学者研究的重要领域之一起源于网络问题、生物学、信息科学、计算机科学所提出的点可区别边染色或强边染色是一个十分困难的间题,在文献【,」中,点可区别边染色和邻点可区别边染色间题得到进一步研究新的染色间题不
2、断被提出,与该问题相关的文献一」中给出了邻点可区别染色、邻点可区别全染色、邻点可区别强全染色等染色的定义及其几类简单图关于此染色的色数,并提出相关猜想年等在文献中提出了一般邻点可区别边染色的定义,并且给出了路、圈、树的一般邻点可区别色指标,对平面图给出了它的一般邻点可区别色指标的上界和下界,同时得到了一个一般的结果如果图连通,且双全,则三双此外,文献还提出了如下猜想猜想如果是连通图,且双全,则三设图认的顶点集合为,边的集合为图矶的一边染色是指集合到集合,,,⋯,岭的一个映射对任意的〔,表示和点相关联的所有边的颜色的集合,称为点的色集合定义如果映射‘
3、、,,,⋯,无满足对任何。,。任,。任,有司关,则称为图的一般邻点可区别边染色,简记为一染色并称而州有一染色为的一般邻点可区别色指标定义图,的一全染色是指集合到集合,,,⋯,料的一个映射对任意的〔,表示和点相关联的所有边及点的颜色的集合,称为点的色集国家自然科学基金资助课题收稿日期一一,收到修改稿日期一一系统科学与数学卷合如果映射日,,,⋯,满足对任何。,任,。任,有。兴,则称为图的一般邻点可区别全染色,简记为一染色并称州有一染色为的一般邻点可区别全染色指标本文将讨论路、圈、星、树、完全图、二部图、轮、扇的一般邻点可区别全染色指标并据此提出猜想本文
4、所涉及的图都是简单的连通有限图本文所用术语与记号参见文献侧主要结论及证明根据定义,显然有以下结论引理设有个连通分支,,,⋯,,则有邵‘卜,,⋯,衬引理若简单连通图含凡,则全定理设表示阶路,全,则证设凡二⋯纵显然凡全,下证凡建立映射、,如下‘,乞二、,乞三。￡。‘,坛,,⋯,一则有‘,落三,‘,,落二所以〔,都有二笋,故凡定理设久表示阶圈,全,则邵久,为偶数氏,为奇数证设氏二⋯纵,分两种情形讨论情形当为偶数时,显然氏全,下证氏建立映射,如下‘,乞三‘,三叭叭,‘,,⋯,一,振。,则有。‘,坛三,,,,乞三所以鞠〔,都有尹。,故,久·情形当。为奇数时,
5、显然氏全,下证久建立映射、,,如下‘,乞二。,,。‘,乞三。。‘。‘,,,⋯,一,。。,则有。‘,葱三,二二,,‘,,艺三所以鞠〔,都有。另,故久定理对于。阶星氏,全,有凡期严谦泰关于图的一般邻点可区别全染色证十阶星,显然凡全,下证二设星心为,其余顶点为”,,⋯,振·建立映射,如下。,,,。。。,,落,,⋯,则有,。‘,,艺,,⋯,,所以鞠任,都有。尹,故,久定理对于阶扇,全有凡证阶扇可看成扇心与路⋯。。的联图显然凡全,下证二建立映射、,,如下。,‘,坛三‘,坛三。。。‘,乞,,⋯,。‘。,,乞,,⋯,则有。,‘二,,乞三,‘,,乞三所以九。任,都
6、有全,故凡定理对于阶轮呱,有二证设轮心为。,轮圈为久二。⋯振,分两种情形讨论情形当三或三时,显然呱全下证呱建立映射升,,如下。,叭,乞三,叭,‘三,叭,‘三,‘,,落,,⋯,,‘。,乞,,⋯,,二,则有。,,,,落三,‘,,乞三,‘,,乞三因为。,或。,,所以。。任,都有全,故呱情形当三时,显然呱全,下证叽建立映射弓,,如下,‘,乞三,乞,‘,乞三,曰上︸‘,艺三,。,‘,几‘‘,葱,,⋯,一,从而。,,,、,落三,乞,‘,,乞三,‘,,乞三,。,所以饰〔,都有。笋,故叽定理对于二部图,巧,,有,巧,证设二部图,巧,中,二。,勿,⋯阮,巧,,。,⋯
7、。。,显然邵,竹,全下证,巧,建立映射升,如下叭,乞,,⋯,二吩,,,⋯,二,任侧卿系统科学与数学卷则有‘,乞,,⋯,,,,乞,,⋯,所以九任,都有。笋,故,,定理对于阶树,全,证阶树瓜也是二部图,由定理可知,几二引理对于。阶完全图瓜,二种色至多产生饥一种可用的色集证设是完全图的一个卜染色,则巍,。〔瓜,司尹哟又。,。任瓜,从而司尹价而二个元素至多产生,一‘个两两相交的集合,从而种色至多产生一种可用的色集定理对于阶完全图凡,全,瓜【【表示不小于的最小整数证第步由引理,显然凡全,下证凡,设顶点集合,,,建立映射日、,,如下哟。,,。,则有。,,,,所
8、以对任意的。〔,都有。尹,故第步采用以下递推方法对凡扩张得到凡,从而可得到凡的一个一增加顶点,与凡中,,都相邻得凡建立映射
