On star polynomials of complements of graphs (Q1123894): Difference between revisions

Let G be a graph. A star cover of G is a spanning subgroup of G in which every component is a star (i.e. a tree with \(n(>1)\) nodes and with n-1 nodes of valency one, or a node). An indeterminate or weight is associated with every star subgroup of G. The weight of a star cover is the product of the weights of its component stars. The star polynomial of G, denoted by E(G), is the sum of the weights of all the possible star covers in G. The authors have derived a formula for \(E(\bar G)\), the star polynomial of the complement \(\bar G\) of a graph G, in terms of the coefficients of E(G). This formula is then used to obtain a result on costar graphs (i.e. graphs with the same star polynomial) and a formula for the number of spanning trees in \(\bar G,\) in terms of certain coefficients in E(G). A simple deduction from the main formula yields a useful formula for the matching polynomial - [\textit{E. J. Farrell}, J. Comb. Theory, Ser. B 27, 75-86 (1979; Zbl 0335.05131)] of \(\bar G,\) in terms of the coefficients of the matching polynomial of G.