Unimodality of the independence polynomials of non-regular caterpillars

MaRDI QIDQ4616097zbMATH OpenFDO

Authors Patrick Bahls, Bailey Ethridge, L. Szabó

Publication date 30 January 2019

Full work available at URL https://arxiv.org/abs/1802.06298, http://ajc.maths.uq.edu.au/pdf/71/ajc_v71_p104.pdf

zbMATH Keywords

unimodular independence polynomials

Mathematics Subject Classification ID

Graph polynomials (05C31)

Abstract: The independence polynomial $I(G,x)$ of a graph $G$ is the polynomial in variable $x$ in which the coefficient $a_n$ on $x^n$ gives the number of independent subsets $SsubseteqV(G)$ of vertices of $G$ such that $|S|=n$. $I(G,x)$ is unimodal if there is an index $mu$ such that that $a_{0}leq{a}_{1}leq$...$leq{a}_{mu-1}leq{a}_{mu}geq{a}_{mu+1}geq$...$geq{a}_{d-1}geq{a}_d$ While the independence polynomials of many families of graphs with highly regular structure are known to be unimodal, little is known about less regularly structured graphs. We analyze the independence polynomials of a large infinite family of trees without regular structure and show that these polynomials are unimodal through a combinatorial analysis of the polynomials coefficients.

Recommendations

• The unimodality of independence polynomials of some graphs
• On the unimodality of independence polynomial of certain classes of graphs
• On the unimodality of independence polynomials of some graphs
• Unimodality of the independence polynomials of some composite graphs
• Unimodality of independence polynomials of very well-covered graphs.

Cites work

• A bipartite graph with non-unimodal independent set sequence
• A family of graphs whose independence polynomials are both palindromic and unimodal
• Clique cover products and unimodality of independence polynomials
• scientific article; zbMATH DE number 5130736 (Why is no real title available?)
• scientific article; zbMATH DE number 5139526 (Why is no real title available?)
• scientific article; zbMATH DE number 4112649 (Why is no real title available?)
• Maximal trees with log-concave independence polynomials
• New families of graphs whose independence polynomials have only real roots
• On the independence polynomials of path-like graphs
• On the unimodality of independence polynomials of some graphs
• Symmetry and unimodality of independence polynomials of path-like graphs
• The independent set sequence of some families of trees
• The roots of the independence polynomial of a clawfree graph
• The unimodality of independence polynomials of some graphs

Cited in

(6)

• On the unimodality of independence polynomial of certain classes of graphs
• Unimodality of independence polynomials of rooted products of graphs
• The independent set sequence of some families of trees
• The unimodality of independence polynomials of some graphs
• On real-rootedness of independence polynomials of rooted products of graphs
• Trees with real rooted independence polynomials

This page was built for publication: Unimodality of the independence polynomials of non-regular caterpillars

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