The independence polynomial of rooted products of graphs
type: Item
instance of: scholarly article
title: The independence polynomial of rooted products of graphs
zbMATH Open document ID: 1201.05048
author: Vladimir R. Rosenfeld
published in: Discrete Applied Mathematics
publication date: 2010-05-05T00:00:00Z
review text: A stable (or independent) set in a graph is a set of pairwise nonadjacent vertices thereof. The stability number \(\alpha(G)\) is the maximum size of stable sets in a graph \(G\). The independence polynomial of \(G\) is \[ I(G;x) = \sum_{k=0}^{\alpha(G)} s_kx^k= s_0+s_1x+s_2x^2+\cdots+ s_{\alpha(G)} x^{\alpha(G)} \quad (s_0:=1), \] where \(s_k\) is the number of stable sets of cardinality \(k\) in a graph \(G\), and was defined by \textit{I. Gutman} and \textit{F. Harary} [Util. Math. 24, 97--106 (1983; Zbl 0527.05055)]. We obtain a number of formulae expressing the independence polynomials of two sorts of the rooted product of graphs in terms of such polynomials of constituent graphs. In particular, it enables us to build infinite families of graphs whose independence polynomials have only real roots.
Mathematics Subject Classification ID: 05C31
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C76
zbMATH DE Number: 5703757
zbMATH Keywords: independence polynomial
zbMATH Keywords: rooted product of graphs
zbMATH Keywords: real independence-polynomial roots
MaRDI profile type: Publication
full work available at URL: j.dam.2009.10.009
OpenAlex ID: W1969007797
cites work: Q3720629
cites work: Roots of independence polynomials of well covered graphs
cites work: Bounding the roots of independence polynomials.
cites work: On the location of roots of independence polynomials
cites work: Average independence polynomials
cites work: The roots of the independence polynomial of a clawfree graph
cites work: Recent results in the theory of graph spectra
cites work: On F-polynomials of thistles
cites work: Q3980550
cites work: An introduction to \(F\)-graphs, a graph-theoretic representation of natural numbers
cites work: A new graph product and its spectrum
cites work: Q3043192
cites work: Q3988150
cites work: Q4033676
cites work: Clique polynomials and independent set polynomials of graphs
cites work: Products of graceful trees
cites work: Q4430893
cites work: Q4452105
cites work: Q4472737
cites work: Q5314090
cites work: On the roots of independence polynomials of almost all very well-covered graphs
cites work: Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture
cites work: Q3424783
cites work: Algorithmic uses of the Feferman-Vaught theorem
cites work: Q5750905
cites work: Q3978339
cites work: The circuit polynomial of the restricted rooted product \(G(\Gamma )\) of graphs with a bipartite core \(G\)
cites work: The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
cites work: On Dependency Graphs and the Lattice Gas
cites work: Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
DOI: 10.1016/J.DAM.2009.10.009
description: scientific article; zbMATH DE number 5703757