一类图的色唯一性  

Chromatic uniqueness of a class graphs

作　　者：魏岭[1] 

机构地区：[1]青海大学成教学院,西宁810001

出　　处：《计算机工程与应用》2013年第22期52-54,共3页Computer Engineering and Applications

摘　　要：如果两个图的色多项式相等,称这两个图色等价。如果与一个图色等价的所有图都与这个图同构,称这个图色唯一。类似的,如果两个图的伴随多项式相等,称这两个图伴随等价。如果与一个图伴随等价的所有图都与这个图同构,称这个图伴随唯一。众所周知,两个图色等价当且仅当它们的补图伴随等价;一个图色唯一当且仅当它的补图伴随唯一。给出了一类图伴随唯一的一个充分必要条件,因而给出了它的补图色唯一的一个充分必要条件。Two graphs are chromatically equivalent if they have the same chromatic polynomials. A graph is said to be chromati- cally unique if each graph which has same chromatic polynomial is isomorphic with it. Similarly, two graphs are adjointly equiv- alent if they have the same adjoint polynomials. A graph is said to be adjointly unique if each graph which has same adjoint poly- nomial is isomorphic with it. As we all know, two graphs are chromatically equivalent if their complement are adjointly equivalent; a graph is chromatically unique if its complement is adjointly unique. In this paper, a necessary and sufficient condition of a classe graphs adjointly unique is given, thus a necessary and sufficient condition of their complement chromatically unique is given.

关 键 词：色多项式 伴随多项式 色唯一 伴随唯一 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]