
For FullText 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 K_{n}
Peng CHENG Shigeru MASUYAMA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E91A
No.9
pp.23142321 Publication Date: 2008/09/01
Online ISSN: 17451337
DOI: 10.1093/ietfec/e91a.9.2314
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: complete graph, connected spanning subgraph, log concave sequence, network reliability polynomial,
Full Text: PDF(336.9KB)>>
Summary:
Let N_{i} be the number of connected spanning subgraphs with i(n1 i m) edges in an nvertex medge undirected graph G=(V,E). Although N_{n1} is computed in polynomial time by the Matrixtree theorem, whether N_{n} is efficiently computed for a graph G is an open problem (see e.g., [2]). On the other hand, whether N_{n}^{2}≥ N_{n1}N_{n+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 K_{n}, we give the formulas for N_{n}, N_{n+1}, by which N_{n}, N_{n+1} are respectively computed in polynomial time on n, and, in particular, prove N_{n}^{2}> N_{n1}N_{n+1} as well.

