A note on the values of independence polynomials at -1

Jonathan Cutler, Nathan Kahl

Research output: Contribution to journalArticleResearchpeer-review

Abstract

The independence polynomial I(G;x) of a graph G is I(G;x)=∑k=0 α(G)skxk, where sk is the number of independent sets in G of size k. The decycling number of a graph G, denoted φ(G), is the minimum size of a set SV(G) such that G-S is acyclic. Engström proved that the independence polynomial satisfies |I(G;-1)|≤2φ(G) for any graph G, and this bound is best possible. Levit and Mandrescu provided an elementary proof of the bound, and in addition conjectured that for every positive integer k and integer q with |q|≤2k, there is a connected graph G with φ(G)=k and I(G;-1)=q. In this note, we prove this conjecture.

Original languageEnglish
Pages (from-to)2723-2726
Number of pages4
JournalDiscrete Mathematics
Volume339
Issue number11
DOIs
StatePublished - 6 Nov 2016

Fingerprint

Polynomials
Polynomial
Graph in graph theory
Q-integers
Independent Set
Connected graph
Integer
Independence

Keywords

  • Decycling number
  • Independence polynomial

Cite this

Cutler, Jonathan ; Kahl, Nathan. / A note on the values of independence polynomials at -1. In: Discrete Mathematics. 2016 ; Vol. 339, No. 11. pp. 2723-2726.
@article{30df8fee304747f5909c075fb8d91169,
title = "A note on the values of independence polynomials at -1",
abstract = "The independence polynomial I(G;x) of a graph G is I(G;x)=∑k=0 α(G)skxk, where sk is the number of independent sets in G of size k. The decycling number of a graph G, denoted φ(G), is the minimum size of a set SV(G) such that G-S is acyclic. Engstr{\"o}m proved that the independence polynomial satisfies |I(G;-1)|≤2φ(G) for any graph G, and this bound is best possible. Levit and Mandrescu provided an elementary proof of the bound, and in addition conjectured that for every positive integer k and integer q with |q|≤2k, there is a connected graph G with φ(G)=k and I(G;-1)=q. In this note, we prove this conjecture.",
keywords = "Decycling number, Independence polynomial",
author = "Jonathan Cutler and Nathan Kahl",
year = "2016",
month = "11",
day = "6",
doi = "10.1016/j.disc.2016.05.019",
language = "English",
volume = "339",
pages = "2723--2726",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "11",

}

A note on the values of independence polynomials at -1. / Cutler, Jonathan; Kahl, Nathan.

In: Discrete Mathematics, Vol. 339, No. 11, 06.11.2016, p. 2723-2726.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - A note on the values of independence polynomials at -1

AU - Cutler, Jonathan

AU - Kahl, Nathan

PY - 2016/11/6

Y1 - 2016/11/6

N2 - The independence polynomial I(G;x) of a graph G is I(G;x)=∑k=0 α(G)skxk, where sk is the number of independent sets in G of size k. The decycling number of a graph G, denoted φ(G), is the minimum size of a set SV(G) such that G-S is acyclic. Engström proved that the independence polynomial satisfies |I(G;-1)|≤2φ(G) for any graph G, and this bound is best possible. Levit and Mandrescu provided an elementary proof of the bound, and in addition conjectured that for every positive integer k and integer q with |q|≤2k, there is a connected graph G with φ(G)=k and I(G;-1)=q. In this note, we prove this conjecture.

AB - The independence polynomial I(G;x) of a graph G is I(G;x)=∑k=0 α(G)skxk, where sk is the number of independent sets in G of size k. The decycling number of a graph G, denoted φ(G), is the minimum size of a set SV(G) such that G-S is acyclic. Engström proved that the independence polynomial satisfies |I(G;-1)|≤2φ(G) for any graph G, and this bound is best possible. Levit and Mandrescu provided an elementary proof of the bound, and in addition conjectured that for every positive integer k and integer q with |q|≤2k, there is a connected graph G with φ(G)=k and I(G;-1)=q. In this note, we prove this conjecture.

KW - Decycling number

KW - Independence polynomial

UR - http://www.scopus.com/inward/record.url?scp=84974589010&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2016.05.019

DO - 10.1016/j.disc.2016.05.019

M3 - Article

VL - 339

SP - 2723

EP - 2726

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 11

ER -