Clique cover products and unimodality of independence polynomials

DOI10.1016/J.DAM.2016.01.030zbMATH Open1335.05135arXiv1309.7673OpenAlexW2286425066MaRDI QIDQ277643FDOQ277643

Bao-Xuan Zhu

Publication date: 2 May 2016

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of monomer-dimer systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• On linear transformations preserving the Pólya frequency property
• Title not available (Why is that?)
• Roots of independence polynomials of well covered graphs
• Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture
• On the corona of two graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Independence polynomials of some compound graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the location of roots of independence polynomials
• On the unimodality of independence polynomials of some graphs
• Building graphs whose independence polynomials have only real roots
• Genus distributions for bouquets of circles
• A unified approach to polynomial sequences with only real zeros
• Clique polynomials and independent set polynomials of graphs
• Polynomials with real zeros and Pólya frequency sequences
• Average independence polynomials
• On the numbers of independent \(k\)-sets in a claw free graph
• Enumeration of digraph embeddings
• On the roots of independence polynomials of almost all very well-covered graphs
• Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs
• On the independence polynomials of path-like graphs
• Title not available (Why is that?)
• Unimodal, log-concave and Pólya frequency sequences in combinatorics
• Log-concavity of genus distributions of ring-like families of graphs
• A new graph product and its spectrum
• Title not available (Why is that?)
• An introduction to chromatic polynomials
• The roots of the independence polynomial of a clawfree graph
• The independence polynomial of rooted products of graphs

Cited In (16)

• 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
• Title not available (Why is that?)
• Independent vertex sets in the Zykov sum
• Unimodality of independence polynomials of rooted products 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)