Y(4,λ)形图簇的伴随多项式的分解及其补图的色等价性

The factorizations of adjoint polynomials of Y(2,2,λ)-shaped graphs and their complements' chromatically eEquivalence

设Pn和Cn是具有n个顶点的路和圈,Sn是n个顶点的的星图,nG表示n个图G的不相交并。EG(r+1)p+r表示把星Sr+1的r个1度点分别与rG的每个分支的第i个顶点重迭,同时把Sr+1的r度点与另一个G的第i个顶点重迭后得到的图,可简记为EGδ,δ=(r+1)(p+r);设m是自然数,图PEG(2 m+1)+(m+1)δ是表示把(m+1)EGδ的每个分支的r+di度顶点分别与P2 m+1的下标为奇数的m+1个顶点重迭后得到的图,记λ=(2 m+1)+(m+1)δ,图Y(4,λ)表示把PEG(2 m+1)+(m+1)δ的两个r+di+1度点与2P3的两个2度点重迭后得到的图,运用图的伴随多项式的性质,讨论了图簇Y(4,λ)∪K1(m为奇数)和Y(4,λ)∪EGδ(m为偶数)的伴随多项式的因式分解式,令m=2k-1 q-1,λk=(2kq-1)+2k-1 qδ,讨论了图簇Y(4,λk)∪(k-1)K1和Y(4,λk)的伴随多项式的因式分解式,进而证明了这些图的补图的色等价性。

Abstract：Let P. be a path with n vertices,C, be a cycle with n vertices,S, be a Star with n vertices, and nG be the union of n graphs G without common vertex. We denoted E^G（r＋1）p＋r as the graph consisting of Sr＋1 and （r＋1）G by coinciding r vertices of degree 1 of Sr＋1 with the ith vertex of every component of rG in turn. Meanwhile the vertex of degree r of Sr＋1 with the ith vertex of G was abbreviated as Eδ^G,δ= （r＋1）p＋r. EG Let m be a nature number,P^EG（2 m＋1）＋（m＋1）δ is the graph consisting of （m＋1）Eδ^G and P2m＋1 by coinciding the vertex of degree r ＋d1 of every component of （m＋1）Eδ^G with m ＋1 vertices which subscript be odd of P^EG（2 m＋1）＋（m＋1）δ and 2P3 by P2m＋1 ,respectively. Let λ=（2 m＋1）＋（m＋1）δ,Y（4,λ） ,is the graph consisting of coinciding two vertices of degree r＋di＋1 of every component of P^EG（2 m＋1）＋（m＋1）δ with two vertices of degree 2 of 2P3, respectively. By using the properties of adjoint polynomials of graphs,we discussed the factoriza- tions of adjoint polynomials of graphs Y（4,λ）∪Ka1 （where m was odd）and Y（4,2）UEδ^G （where m was even ）. Let m=2^k-1 q-1andλk=（2^nq-1）＋2^n-1 qδ,we further studied the factorizations of adjoint polynomials of graphs Y（4,λk）∪（k-1）K1and Y（4,λk）. We proved chromatically equivalence of complements of these graphs.