For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2008/09/01
Online ISSN: 1745-1337
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)>>
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., ). On the other hand, whether Nn2≥ Nn-1Nn+1 for a graph G is also open as a part of log concave conjecture (see e.g., ,). 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.