Research On The Critical Group And Chromatical Uniqueness Of A Graph

The critical group and chromatic polynomial are two important parameters reflecting the character of graphs. There were not many results since the people began the research of critical groups, back in 1990's; however, a lot of results about chromatic polynomial have been got as there is a long history since the study on chromatic polynomial started. A central aspect regarding critical group is calculating the critical group of a certain graph. And about chromatic polynomial, to determine the class of graphs which areχ-unique is the thing people interest in.The order of critical group is equal to the number of spanning trees of a graph. Two graphs which have different number of spanning trees must not be isomorphism, even two graphs which have the same number of spanning trees but different critical groups are definitely not isomorphism. In this article, we will get the critical groups of graphs Km V Pn and Pm∨Pn(m≥4,n≥5). The results are in the following:The critical group of Km V Pn is And its spanning tree number isThe critical group of Pm∨Pn is Z/tZ(?)Z/sZ, where t= (bn-2, cd-1, am-2), s= And its spanning tree number is where the parameters an,bn,c,d will be explained in section 2.3. Until now,people have not found a proper way to determine whether a graph isχ-unique or not,so we only get a fewχ-unique graphs. Luckily,the K4-homeomorphs whose girth is less than 7 have been fully settled.In this arti-cle,K4-homeomorphs with girth 8 is also given:K4-homeomorphs K4(2,3,3,d,e,f)with girth 8 is notχ-unique if and only if it is isomorphic to K4(2,3,3,1,6,α)(α≥6),K4(2,3,3,1,β,β+2)(β≥4),or K4(2,3,3,1,5,6).K4-homeomorphs K4(1,2,5,d,e,f)which has exactly one path of length 1 and girth 8 is not chromatically unique if and only if it is K4(1,2,5,α,α+6,α1)(α≥2),K4(1,2,5,β+2,β,β+5)(β≥2),K4(1,2,5,γ,γ+1,γ+6)(γ≥3), K4(1,2,5,δ+5,δ,δ+2)(δ≥3),K4(1,2,5,σ,σ+1,σ+3)(σ≥3),K4(1,2,5,η-2,η+2,η)(η≥3),K4(1,2,5,4,λ,3)(λ≥4),K4(1,2,5,4,3,7),K4(1,2,5,4,4,7) and K4(1,2,5,4,6,4)K4-homeomorphs K4(1,3,4,d,e,f)which has girth 8 and exactly one path of length 1 is notχ-unique if and only if it is K4(1,3,4,α,α+1,2)(α≥4), K4(1,3,4,β,β+1,β+4)(β≥2),K4(1,3,4,γ+2,γ,γ+4)(γ≥2),K4(1,3,4,ε2,ε+3,ε)(ε≥2),K4(1,3,4,η,η+5,η+1)(η≥2),K4(1,3,4,6,2,6),K4(1,3,4,2,5,8), and K4(1,3,4,2,7,5).K4-homeomorphs K4(1,2,c,2,e,3)which has girth 8 is notλ-unique if and only if it is K4(1,2,α,2,α+3,3)(α≥5).K4-homeomorphs K4(1,2,c,3,e,2)which has girth 8 isχ-unique.K4-homeomorphs K4(2,2,4,d,e,f)which has girth 8 is notχ-unique if and only if it is K4(2,2,4,β,1,β+2)(β≥5).