Fm∨Pn的点可区别边色数.pdf.pdf

维普资讯
第��卷第�期�大�学�数�学����.��,��.��
����年�月������������������������.�����
������的点可区别边色数�
田京京�,�邓方安�,�张忠辅�,�陈祥恩。�
��.陕西理工学院数学系,汉中������; �.兰州交通大学应用数学研究所,兰州������;�
�.西北师范大学数学与信息科学学院,兰州��������
�摘�要�研究了�����的点可区别边染色,给出了�����的点可区别边色数.�
�关键词�图;扇;路;联图;点可区别边染色;点可区别边色数�
�中图分类号�����.���文献标识码����文章编号�����—������������—����—���
��引�言�
�
了解决网络权的分配问题,������,������等人先后提出点可区别边染色�或强边染色�得到了若干结�
果,并提出了有关猜想����.本文研究了�����的点可区别边染色,给出�����的点可区别边色数.�
定义����设厂是图�的一个是一正常边染色,且满足���,�∈����,“≠�,其中��“�≠����;则�
�的点可区别边染色,简记为是一���������,而����一����是�是一����������称为�的点�
可区别边色数,其中��“�一�厂�������������.�
显然,对于������≥�的连通图,����存在.�
猜想�卜�若�是一个连通图,且������≥�,那么����≤����≤������.�
定义�����设�和�是点边都不相交的简单图,�
�������一���������,��������一����������������∈����,�/�∈�����,�
则称����是�与�的联图.�
在这篇文章里我们研究了������的点可区别边染色,给出了�������
有加说明的术语和记号可参见���.�
��主要结论�
引理���对�≥�的�阶完全图��,有�
���一��’�’:三�����。�����.��
记�
�����一�����一�,�,⋯,��,�
�����一��������一�,⋯,�����������一�,⋯,�一��,�
�����一���一�,�,⋯,��, ������������一�,�,⋯,�一��.�
以下总设�≥�,�≥�.�
�收稿日期�����—��—���
�基金项目�国家自然科学基金资助项目����������;陕西理工学院博士基金启动项目������������
维普资讯
第�期�田京京,等:�����的点可区别边色数����
定理��当���一�,有�
��。�一�。�
;���������一����。���.�
证分两种情况考虑:�
情况��当�一�,”一�时,�����一��.由引理�知结论为真,即���������一;������一�.�
情况��当���时,通过计算,有�
�������一�������������≥��,���������