A proof of unimodality on the numbers of connected spanning subgraphs in an n-vertex graph with at least (3-2 2) n^2 + n - 7-2 22 2 edges

DOI10.1016/J.DAM.2009.11.008MaRDI QIDQ968184zbMATH OpenOpenAlexFDO

Authors 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) Combinatorial aspects of matroids and geometric lattices (05B35) Enumeration in graph theory (05C30)

Recommendations

• On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
• Two-connected spanning subgraphs with at most \(\frac{10}{7}{\mathrm{OPT}}\) edges
• scientific article; zbMATH DE number 7714103
• On the number of edges in a graph with no \((k + 1)\)-connected subgraphs
• On 2-connected spanning subgraphs with bounded degree in \(K _{1,r }\)-free graphs
• The number of connected sparsely edged uniform hypergraphs
• On the sum-connectivity index of unicyclic graphs with \(k\) pendent vertices
• Bound for the algebraic connectivity of Nordhaus-Gaddum type for unicyclic graphs
• On Minimum Spanning Subgraphs of Graphs With Proper Connection Number 2
• On the general sum-connectivity index of connected unicyclic graphs with \(k\) pendant vertices

Cites work

• scientific article; zbMATH DE number 3836093 (Why is no real title available?)
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 4091530 (Why is no real title available?)
• scientific article; zbMATH DE number 1295362 (Why is no real title available?)
• scientific article; zbMATH DE number 568836 (Why is no real title available?)
• scientific article; zbMATH DE number 617592 (Why is no real title available?)
• scientific article; zbMATH DE number 718851 (Why is no real title available?)
• scientific article; zbMATH DE number 3368629 (Why is no real title available?)
• An extension of a criterion for unimodality
• An introduction to chromatic polynomials
• Broken-Cycle-Free Subgraphs and the Log-Concavity Conjecture for Chromatic Polynomials
• Chromatic polynomials and logarithmic concavity
• Chromatic, Flow and Reliability Polynomials: The Complexity of their Coefficients
• Parallel concepts in graph theory
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Reliability Computations in Planar and Acyclic Graphs

Cited in

(2)

• On the unimodality of domination polynomials
• The unimodality of \(N(G,k)\) and an identity on two kinds of Stirling numbers

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

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