若干图的伴随分解及色等价性

Adjoint factorizations of some graphs and chromatically equivalence of their complements

设Pm和Cm分别表示具有m个顶点的路和圈,G是任意的r阶连通图,设m是正奇数,把路Pm的标号为奇数的2-1(m+1)个顶点分别与2-1(m+1)G每个分支的第i个顶点Vi重迭后所得到的图记为ρG(i)m+2-1(m+1)r。运用图的伴随多项式的性质,首先给出了一类图簇ρG(i)(2 m+2)+((m+1)r的伴随多项式。进而令m=2t-1 q-1,λn=(2nq-1)+2n-1 qr,在讨论上述图的伴随多项式的基础上,我们证明了图ρG(i)λt和ρG(i)λt∪(t-1)K1的伴随多项式的因式分解定理,进而证明了这些图类的补图的色等价性。

It used the symbol Pm to denote a path with n vertices and Cm to denote a cycle with n vertices. In addition,G was a connectiwe graph with r vertices and let be an odd number, then these were denoted by ρ（m＋2）^GG -1 （m＋1）.The graph consisting of Pm and 2^- 1 （m＋1）G by coinciding m vertices were marked ＂odd ＂ with the vertex Vi of every component of Pm and 2^- 1 （m＋1）G,respectively. By applying the properties of adjoint polynomials,we gave the adjoint polynomials of a kind of graphs ρ （2m＋2）^GG＋（（m＋1））r,Let m=2^（t-1） q-1 and λn=（2^n q-1） ＋2^（n-1） qr,which was based on the several adjoint polynomials of graphs discussed above. It also proved the factorizations Theorem of adjoint polynomials of graphs ρλt^GG and ρλt^GG ∪（t-1）K1,Furthermore,the chromatically equivalenl graphs of their complements were therefore verified.