The search functionality is under construction.

The search functionality is under construction.

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}^{2}≥ *N*_{n-1}*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*_{n-1}*N*_{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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

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}^{2}≥ *N*_{n-1}*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*_{n-1}*N*_{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}^{2}≥ *N*_{n-1}*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*_{n-1}*N*_{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}^{2}≥ *N*_{n-1}*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*_{n-1}*N*_{n+1} as well.

ER -