单圈图的伴随多项式的极小根(英文)

开篇：润墨网以专业的文秘视角，为您筛选了一篇单圈图的伴随多项式的极小根(英文)范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

AbstractThe adjoint polynomial was introduced for solving the chromaticity problem of the complements of graphs. The minimum roots of the adjoint polynomials of graphs can be applied to sort out graphs that are not chromatically equivalent. Letβ（G） be the minimum root of the adjoint polynomial of the graph G. Denote by？n the set of all unicyclic graphs on n vertices. All graphs with max{β（G）|G∈？n}（resp. min{β（G）|G∈？n}） are determined.

Key wordsChromatic polynomial； Adjoint polynomial； Unicyclic graphs； Roots

CLC numberO 157.5Document codeA

1Introduction

All the graphs considered here arefinite， undirected and simple. Undefined notation and terminology will refer to those in [1]. Let G be a graph， and G， V （G） and E（G）， respectively， be the complement， the vertex set and the edge set of G. The chromatic polynomial of G is defined as[2]

George David Birkhoffintroduced the chromatic polynomial in 1912， defining it only for planar graphs， in an attempt to prove the four color theorem. In 1968 Read asked which polynomials are the chromatic polynomials of some graph， a question that remains open， and introduced the concept of chromatically equivalent graphs[2]. Today， chromatic polynomials are one of the central objects of algebraic graph theory. The adjoint polynomial was introduced for solving the chromaticity problem of the complements of graphs[3，4]. For a survey of the mathematical properties and related results see the review [4]. Letβ（G） be the minimum root of the adjoint polynomial of the graph G. The minimum roots of the adjoint polynomials of graphs can be applied to sort out graphs that are not chromatically equivalent. In[5？8]， the authors studied the minimum real roots of the adjoint polynomials of some graphs， many new classes of chromatically unique（chromatically equivalent） graphs had been obtained by comparing the minimum roots of their adjoint polynomials. Thus， it is useful tofind the extremal values ofβ（G） for significant classes of graphs G. A connected graph with n vertices is said to be unicyclic if it has n edges. Let？nbe the set of all unicyclic graphs on n vertices. In this paper， all graphs with max{β（G）|G∈？n}， or just maxβ（？n）（resp. min{β（G）|G∈？n}， or just minβ（？n）） are determined.

For a connected graph G， let e = uv∈E（G）. We carry out the following transformations on G. Contracting the edge e = uv（i.e. identifying u with v） and adding a pendent edge to the vertex u（= v）， the resulted graph is denoted by G0（as shown in Figure 1（a））.

Lemma 6[11]Let G and G0be two graphs as shown in Figure 1（a）. If u and v do not belong to any triangle in G， thenβ（G） >β（G0）.

References

[1] Bondy J A and Murty U S R. Graph Theory with Application. North-Holland， Amsterdam， 1976.

[2] Read R C. An introduction to chromatic polynomials. J Comb Theory， 1968， 4： 52-71.

[3] Liu R. A new method forfinding chromatic polynomial of graphs and its applications（in Chinese）. Kexue Tongbao， 1987， 32： 1508-1509.

[4] Liu R， Zhao L. A new method for proving chromatic uniqueness of graphs. Disc Math， 1997， 171： 169-177.

[5] Wang S Z， Liu R. Chromatic uniqueness of complementary graphs of cycle and Dn（in Chinese）. J Math Res Exposition， 1998， 18（2）： 296.

[6] Zhao H， Huo B， Liu R. Chromaticity of the complements of paths. J Math Study， 2000， 4： 345-353.

[7] Zhao H， Li X， Zhang S， Liu R. On the minimum real roots of theσ-polynomials and chromatic uniqueness of graphs. Disc Math， 2004， 281： 277-294.

[8] Ma H C， Ren H Z. The chromatic equivalence classes of the complements of graphs with the minimum real roots of their adjoint polynomials greater than -4. Disc Math， 2008， 308： 1830-1836.

[9] Ren H Z， Liu R. On extremes of the minimum real roots of the adjoint polynomials of graphs with R（G）≥1. Math Res Exposition（in Chinese）， 2006， 26： 819-824.

[10] Ren H Z， Liu R. On the minimum real roots of the adjoint polynomials of graphs. Math Res Exposition， 2008， 28： 987–993.

[11] Ren H Z. On orderings of some graphs by the extreme roots of their graph polynomials. IEEE Computer Society， 2009， CIS（1）： 272-276.

[12] Liu R. Some results on the adjoint polynomials of graphs. J Qinghai Norm Univ， 1992， 1： 1-6.