On star polynomials of complements of graphs
type: Item
instance of: scholarly article
title: On star polynomials of complements of graphs
zbMATH Open document ID: 0678.05005
DOI: 10.1007/BF02386118
author: E. J. Farrell
author: C. M. de Matas
published in: Arkiv för Matematik
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05A99
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4110698
zbMATH Keywords: simple cover
zbMATH Keywords: star cover
zbMATH Keywords: matching polynomial
MaRDI profile type: Publication
cites work: An introduction to matching polynomials
cites work: On a Class of Polynomials Associated with the Stars of a Graph and its Application to Node-Disjoint Decompositions of Complete Graphs and Complete Bipartite Graphs into Stars
full work available at URL: https://doi.org/10.1007/bf02386118
OpenAlex ID: W2037840356
description: scientific article; zbMATH DE number 4110698