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.008zbMATH Open1225.05134OpenAlexW2017061446MaRDI QIDQ968184FDOQ968184

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

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

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)

Cites Work

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

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)