Upper bounds for the independence polynomial of graphs at -1

DOI10.1007/S40840-021-01106-XMaRDI QIDQ2049008zbMATH OpenOpenAlexFDO

Authors Fayun Cao, Han Ren

Publication date 24 August 2021

Published in Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s40840-021-01106-x

zbMATH Keywords

cyclomatic numberdecycling numberindependence polynomialnon-\(\tilde{3}\)-cycles

Mathematics Subject Classification ID

Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• A note on the values of independence polynomials at \(-1\)
• The cyclomatic number of a graph and its independence polynomial at - 1
• A simple proof of an inequality connecting the alternating number of independent sets and the decycling number
• On a conjecture of Levit and Mandrescu
• Some results on the independence polynomial of unicyclic graphs

Cites work

• A bound on the values of independence polynomials at -1/k for k-degenerate graphs
• A note on the values of independence polynomials at \(-1\)
• A simple proof of an inequality connecting the alternating number of independent sets and the decycling number
• Graph theory with applications
• scientific article; zbMATH DE number 3836093 (Why is no real title available?)
• scientific article; zbMATH DE number 3873364 (Why is no real title available?)
• scientific article; zbMATH DE number 5130736 (Why is no real title available?)
• scientific article; zbMATH DE number 4074878 (Why is no real title available?)
• scientific article; zbMATH DE number 3745213 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 528857 (Why is no real title available?)
• Independence polynomials of some compound graphs
• Mehler formulae for matching polynomials of graphs and independence polynomials of clawfree graphs
• Reducibility among combinatorial problems
• The cyclomatic number of a graph and its independence polynomial at - 1
• The independence polynomial of rooted products of graphs
• Upper bounds on the Witten index for supersymmetric lattice models by discrete Morse theory

Cited in

(9)

• A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
• An upper bound on the independence number of a graph computable in polynomial-time
• The cyclomatic number of a graph and its independence polynomial at - 1
• A note on the values of independence polynomials at \(-1\)
• On the independence polynomial of an antiregular graph
• On a conjecture of Levit and Mandrescu
• A bound on the values of independence polynomials at -1/k for k-degenerate graphs
• A simple proof of an inequality connecting the alternating number of independent sets and the decycling number
• A note on the alternating number of independent sets in a graph

This page was built for publication: Upper bounds for the independence polynomial of graphs at \(-1\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2049008)