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

Peng CHENG; Shigeru MASUYAMA

doi:10.1093/ietfec/e91-a.9.2314

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

Full Text Views

0

Cite this

Summary :

Let N_i 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 N_n-1 is computed in polynomial time by the Matrix-tree 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²≥ N_n-1N_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²> N_n-1N_n+1 as well.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.9 pp.2314-2321

Publication Date: 2008/09/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e91-a.9.2314

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Peng CHENG, Shigeru MASUYAMA, "Formulas for Counting the Numbers of Connected Spanning Subgraphs with at Most n+1 Edges in a Complete Graph Kn" in IEICE TRANSACTIONS on Fundamentals, vol. E91-A, no. 9, pp. 2314-2321, September 2008, doi: 10.1093/ietfec/e91-a.9.2314.
Abstract: Let N_i 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 N_n-1 is computed in polynomial time by the Matrix-tree 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²≥ N_n-1N_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²> N_n-1N_n+1 as well.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.9.2314/_p

Copy

@ARTICLE{e91-a_9_2314,
author={Peng CHENG, Shigeru MASUYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Formulas for Counting the Numbers of Connected Spanning Subgraphs with at Most n+1 Edges in a Complete Graph Kn},
year={2008},
volume={E91-A},
number={9},
pages={2314-2321},
abstract={Let N_i 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 N_n-1 is computed in polynomial time by the Matrix-tree 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²≥ N_n-1N_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²> N_n-1N_n+1 as well.},
keywords={},
doi={10.1093/ietfec/e91-a.9.2314},
ISSN={1745-1337},
month={September},}

Copy

TY - JOUR
TI - Formulas for Counting the Numbers of Connected Spanning Subgraphs with at Most n+1 Edges in a Complete Graph Kn
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2314
EP - 2321
AU - Peng CHENG
AU - Shigeru MASUYAMA
PY - 2008
DO - 10.1093/ietfec/e91-a.9.2314
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2008
AB - Let N_i 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 N_n-1 is computed in polynomial time by the Matrix-tree 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²≥ N_n-1N_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²> N_n-1N_n+1 as well.
ER -