图Ψ^(*S^*)(4δ,nδ)∪tS_δ~*的伴随多项式的分解及色等价性分析

Factorization of adjoint polynomials of graph Ψ^(*S^*)(4δ,nδ)∪tS_δ~* and chromatically equivalence analysis

设Pn是具有n个顶点的路,Ψ*(4,n)表示把2P3的两个2度点分别与Pn的两个1度点重迭后得到的图,Sδ*(δ=rm+1)表示把rPm+1的每个分支的一个1度点重迭在一起得到的图。用PnSδ*表示把Pn的n个顶点与nSδ*的每一个分支的r度顶点依次重迭后得到的图,并用Ψ*S*(4δ,nδ)表示把图Ψ*(4,n)的n+4个顶点与(n+4)Sδ*的每一个分支的r度顶点依次重迭后得到的图。运用图的伴随多项式的性质,证明了图PnSδ*∪tSδ*与Ψ*S*(4δ,nδ)∪tSδ*的伴随多项式的因式分解定理,进而得到了这类图的补图的色等价图的结构特征。

Assume P. to be the path with n vertices and Ψ＊ （4,n） be the graph consisting of 2P3 and P. by coinciding two vertices of degree 2P3 of with two vertices of degree 1 of Pn, respectively. Sδ＊（δ=rm＋1） Use to denote the graph, consisting of rPm＋1 by coinciding one vertex of degree 1 of each component of rPm＋1. The graph,consisting of Pn and nS; by coinciding each vertex of Pn with the vertex of degree r of every component of nS_δ^＊,respectively,was labelled as PnSδ＊. The symbol Ψ＊S^＊（4δ,nδ） was applied to ad- dress the graph obtained from Ψ^＊ （4,n） and （n＋4）Sδ＊ by coinciding each vertex ofΨ^＊（4,n） with the vertex of degree r of every component of Ψ^＊ （4,n）,respectively. By adopting the properties of adjoint polynomials. We proved that the factorization theorem of adjoint polynomials of two kinds of graphs PnSδ＊∪tSδ＊; and Ψ＊S＊（4δ, nδ） ∪tSδ＊（n = 2^1 q- 1）. Furthermore, the structural characteristics of chromatically equivalent graphs of their complements were obtained.