Clique cover products and unimodality of independence polynomials

DOI10.1016/J.DAM.2016.01.030MaRDI QIDQ277643zbMATH OpenOpenAlexFDO

Authors Bao-Xuan Zhu

Publication date 2 May 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.7673

zbMATH Keywords

symmetrylog-concavityunimodalityindependence polynomialsreal zeros

Mathematics Subject Classification ID

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

Abstract: Given two graphs $G$ and $H$, assume that $mathscrC=C_1,C_2,ldots,C_q$ is a clique cover of $G$ and $U$ is a subset of $V(H)$. We introduce a new graph operation called the clique cover product, denoted by $G^{mathscrC}star{H}^U$, as follows: for each clique $C_{i}inmathscrC$, add a copy of the graph $H$ and join every vertex of $C_i$ to every vertex of $U$. We prove that the independence polynomial of $G^{mathscrC}star{H}^U$ ${\displaystyle }$I(G^{mathscr{C}}star H^U;x)=I^q(H;x)I(G;frac{xI(H-U;x)}{I(H;x)}),${\displaystyle }$ which generalizes some known results on independence polynomials of corona and rooted products of graphs obtained by Gutman and Rosenfeld, respectively. Based on this formula, we show that the clique cover product of some special graphs preserves symmetry, unimodality, log-concavity or reality of zeros of independence polynomials. As applications we derive several known facts in a unified manner and solve some unimodality conjectures and problems.

Recommendations

• Unimodality of independence polynomials of the cycle cover product of graphs
• Unimodality of independence polynomials of the incidence product of graphs
• Domination polynomial of clique cover product of graphs
• scientific article; zbMATH DE number 2094520
• Unimodality of the independence polynomials of some composite graphs

Cites work

• scientific article; zbMATH DE number 3836093 (Why is no real title available?)
• scientific article; zbMATH DE number 4112649 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (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?)
• scientific article; zbMATH DE number 568836 (Why is no real title available?)
• scientific article; zbMATH DE number 1990727 (Why is no real title available?)
• scientific article; zbMATH DE number 3073200 (Why is no real title available?)
• A family of graphs whose independence polynomials are both palindromic and unimodal
• A new graph product and its spectrum
• A unified approach to polynomial sequences with only real zeros
• An introduction to chromatic polynomials
• Average independence polynomials
• Building graphs whose independence polynomials have only real roots
• Clique polynomials and independent set polynomials of graphs
• Enumeration of digraph embeddings
• Genus distributions for bouquets of circles
• Graph theory
• Independence polynomials of some compound graphs
• Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture
• Log-concavity of genus distributions of ring-like families of graphs
• Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs
• On linear transformations preserving the Pólya frequency property
• On the corona of two graphs
• On the independence polynomials of path-like graphs
• On the location of roots of independence polynomials
• On the numbers of independent k-sets in a claw free graph
• On the roots of independence polynomials of almost all very well-covered graphs
• On the unimodality of independence polynomials of some graphs
• Polynomials with real zeros and Pólya frequency sequences
• Roots of independence polynomials of well covered graphs
• Symmetry and unimodality of independence polynomials of path-like graphs
• The independence polynomial of rooted products of graphs
• The roots of the independence polynomial of a clawfree graph
• The unimodality of independence polynomials of some graphs
• Theory of monomer-dimer systems
• Unimodal, log-concave and Pólya frequency sequences in combinatorics
• Unimodality of independence polynomials of very well-covered graphs.

Cited in

(17)

• Trees with real rooted independence polynomials
• More on the unimodality of domination polynomial of a graph
• Unimodality of the independence polynomials of non-regular caterpillars
• On the independent domination polynomial of a graph
• Log-concavity of independence polynomials of some kinds of trees
• On trees with real-rooted independence polynomial
• Independent vertex sets in the Zykov sum
• scientific article; zbMATH DE number 2094520 (Why is no real title available?)
• Unimodality of independence polynomials of rooted products of graphs
• Domination polynomial of clique cover product of graphs
• On the independent set sequence of a tree
• Total coloring conjecture on certain classes of product graphs
• Unimodality of independence polynomials of the incidence product of graphs
• On real-rootedness of independence polynomials of rooted products of graphs
• The roller-coaster conjecture revisited
• Unimodality of independence polynomials of the cycle cover product of graphs
• The independent set sequence of some families of trees

This page was built for publication: Clique cover products and unimodality of independence polynomials

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