A proof of unimodality on the numbers of connected spanning subgraphs in an \(n\)-vertex graph with at least \(\left\lceil (3-2\sqrt 2) n^2 + n - \frac {7-2\sqrt 2}{2 \sqrt 2}\right\rceil\) edges

DOI10.1016/j.dam.2009.11.008zbMath1225.05134OpenAlexW2017061446MaRDI QIDQ968184

Peng Cheng, Shigeru Masuyama

Publication date: 5 May 2010

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

Full work available at URL: https://doi.org/10.1016/j.dam.2009.11.008

zbMATH Keywords

unimodal sequencelog concave sequenceconnected spanning subgraphsnetwork reliability polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31) Enumeration in graph theory (05C30) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Parallel concepts in graph theory
• Chromatic polynomials and logarithmic concavity
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Chromatic, Flow and Reliability Polynomials: The Complexity of their Coefficients
• Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials
• The Complexity of Reliability Computations in Planar and Acyclic Graphs
• An introduction to chromatic polynomials
• An extension of a criterion for unimodality
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A proof of unimodality on the numbers of connected spanning subgraphs in an \(n\)-vertex graph with at least \(\left\lceil (3-2\sqrt 2) n^2 + n - \frac {7-2\sqrt 2}{2 \sqrt 2}\right\rceil\) edges