Formulas for Counting the Numbers of Connected Spanning Subgraphs with at Most n+1 Edges in a Complete Graph Kn

Peng CHENG  Shigeru MASUYAMA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.9   pp.2314-2321
Publication Date: 2008/09/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.9.2314
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
complete graph,  connected spanning subgraph,  log concave sequence,  network reliability polynomial,  

Full Text: PDF(336.9KB)>>
Buy this Article

Let Ni be the number of connected spanning subgraphs with i(n-1 i m) edges in an n-vertex m-edge undirected graph G=(V,E). Although Nn-1 is computed in polynomial time by the Matrix-tree theorem, whether Nn is efficiently computed for a graph G is an open problem (see e.g., [2]). On the other hand, whether Nn2Nn-1Nn+1 for a graph G is also open as a part of log concave conjecture (see e.g., [6],[12]). In this paper, for a complete graph Kn, we give the formulas for Nn, Nn+1, by which Nn, Nn+1 are respectively computed in polynomial time on n, and, in particular, prove Nn2> Nn-1Nn+1 as well.