证明图ρ_n^G(i)∪G等的伴随分解及色等价性  

Proof of the Adjoint Factorizations of Graphs ρ_n^G(i) ∪G Etc and Chromatically Equivaleness

作　　者：郝翠菊[1] 张秉儒[2] 

机构地区：[1]青海大学成教学院,青海西宁810006 [2]青海师范大学数学系,青海西宁810008

出　　处：《数学的实践与认识》2015年第7期223-230,共8页Mathematics in Practice and Theory

基　　金：国家自然科学基金(10671008)

摘　　要：设P_m和C_m分别表示具有m个顶点的路和圈,G是任意的r阶连通图,设m是偶数,把路P_(m-1)的标号为偶数的2^(-1)m个顶点分别与2^(-1)mG每个分支的第i个顶点V_i重迭后的图记为ρ_((m-1)+2^(-1)mr)~G(i),令n=(2m+1)+(m+1)r,把图kρ_n^G(i)的每个分支的一个d(v_i)+1度顶点分别与S_(k+1)的k个1度点重迭后所得到的图记为Y_(kn+1)^(PG),运用图的伴随多项式的性质,首先给出了一类图簇ρ_n^G(i)和Y_(kn+1)^(PG)的伴随多项式.在讨论上述图的伴随多项式的基础上,证明了图ρ_n^G(i)∪G、Y_(kn+1)^(PG)∪(k-1)K_1和Y_(kn+1)^(PG)∪(k-1)K_1∪(k-1)G的伴随多项式的因式分解定理,进而证明了这些图类的补图的色等价性.We use the symbol Pm to denote a path with n vertices and Cm to denote a cycle with n vertices, and G be a connective graph with r vertices, and let m be an odd number, and let denote by P（m-1）＋2^-1^G（i）mr the graph consisting of Pm-1 and 2^-1mG by coinciding 2^-1m vertices are marked ＂odd ＂ with the ith vertex Vi of every component of 2^-1mG, respectively; Let n （2m ＋ 1）＋ （m ＋ 1）r, and let denote by Pkn＋1^PG the graph consisting of kρn^G（i）and Sk＋1 by coinciding a vertex of degree d（vi） ＋ 1 of every component of k ρn^G（i）with k vertices of degree 1, respectively; By applying the properties of adjoint polynomials, We give and prove the factorizations Theorem of adjoint polynomials of graphs ρn^G（i）and Ykn＋1^PG, based on the above discussed several adjoint polynomials of graphs, We prove Chromatically equivalence of the graphs ρn^G（i）∪ G、 Ykn＋1^pg∪（k - 1）K1and Ykn＋1^PG∪（k-1）K1∪（k-1）G, prove chromatically equivalent graphs of their complements.

关 键 词：色多项式 伴随多项式 因式分解 色等价性 

分 类 号：O157.5[理学—数学]