de Bruijn定理的推广(英文)  

A Generalized Form of de Bruijn's Theorem

作　　者：杜清晏[1] 

机构地区：[1]内蒙古大学数学系,呼和浩特内蒙古010021

出　　处：《数学进展》2008年第6期729-748,共20页Advances in Mathematics（China）

基　　金：supported by NSFC(No.19571042).

摘　　要：de Bruijn定理是一种重要的组合计数方法,本文以非常自然的方式推广了这种方法.P-图是图G在其顶点上的置换群P作用下形成的轨道.文中引进了P-图,P-图的色容指标,P-图关于色置换群H的色权多项式以及色对称与全色对称图等概念,建立了色权多项式的计算公式和一系列的组合公式及性质.de Bruijn＇s Theorem is generalized in a harmonious way in this paper. Rel- evant new notions such as de Bruijn coloring of a graph, the chromatic capacity index of a P-graph, chromatic symmetric and chromatic totally symmetric graphs are introduced. Reduction Theorems and the expression of the chromatic capacity index of a P-graph are given. The expressions of the chromatic function and the chromatic weight polynomial of a P-graph about a permutation group H are established, de Bruijn＇s Theorem follows from these expressions as a special case when the graph is empty. Finally, some elementary properties of the chromatic functions are presented.

关 键 词：组合计数 DE BRUIJN图 色等价类 色权多项式 

分 类 号：O174[理学—数学] O157[理学—基础数学]