A proof of unimodality on the numbers of connected spanning subgraphs in an n-vertex graph with at least inverted right perpendicular(3-2 root 2)n(2) + n-7-2 root 2/2 root 2inverted left perpendicular edges

作者：Cheng Peng^*; Masuyama Shigeru

来源：Discrete Applied Mathematics, 2010, 158(6): 608-619.

DOI：10.1016/j.dam.2009.11.008

• Connected spanning subgraphs
• Unimodal sequence
• Log concave sequence
• Network reliability polynomial

Consider a connected undirected simple graph G = (V, E) with n vertices and m edges, and let N-i denote the number of connected spanning subgraphs with i (n - 1 <= i <= m) edges in G. Two well-known open problems are whether Nn-1, N-n, ... , N-m is unimodal (posed by Welsh (1971)[21]), and whether iris log concave (posed by Mason (1972)[13]). Here, a sequence of real numbers a(0), a(1), ... , a(m), is said to be unimodal if there is an index i (0 <= i <= m) such that a(0) <= a(1) <= ... <= a(i) >= a(i+1) >= ... >= a(m), and log concave if a(i)(2) >= a(i-1)a(i+1) for all indices i (0 < i < m). In this paper, for an n-vertex graph G, we prove that Nn-1, N-n, ... , N-m, is unimodal if G has at least inverted right perpendicular(3 - 2 root 2)n(2) + n - 7-2 root 2/2 root 2inverted left perpendicular edges, and log concave if n <= 7, which implies that it is unimodal as well.

• 出版日期2010-3-28