Properties on the Average Number of Spanning Trees in Connected Spanning Subgraphs for an Undirected Graph

Peng CHENG; Shigeru MASUYAMA

Properties on the Average Number of Spanning Trees in Connected Spanning Subgraphs for an Undirected Graph

Peng CHENG, Shigeru MASUYAMA

Full Text Views

0

Cite this

Summary :

Consider an undirected graph G=(V,E) with n (=|V|) vertices and m (=|E|) edges. It is well-known that the problem of computing the sequence N_n-1,N_n,...,N_m is #P-complete (see e.g.,[3]), where N_i denotes the number of connected spanning subgraphs with i (n-1!im) edges in G. In this paper, by proving new inequalities on the sequence N_n-1,N_n,...,N_m, we show an interesting and stronger property that the sequence γ_n-1,γ_n,...,γ_m, where γ_i denotes the average number of spanning trees in the connected spanning subgraphs with i edges, is a convex sequence as well as a monotonically increasing sequence, although this property does not hold for the sequence N_n-1,N_n,...,N_m.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E86-A No.5 pp.1027-1033

Publication Date: 2003/05/01

Publicized

Online ISSN

DOI

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

Category

Cite this

Copy

Peng CHENG, Shigeru MASUYAMA, "Properties on the Average Number of Spanning Trees in Connected Spanning Subgraphs for an Undirected Graph" in IEICE TRANSACTIONS on Fundamentals, vol. E86-A, no. 5, pp. 1027-1033, May 2003, doi: .
Abstract: Consider an undirected graph G=(V,E) with n (=|V|) vertices and m (=|E|) edges. It is well-known that the problem of computing the sequence N_n-1,N_n,...,N_m is #P-complete (see e.g.,[3]), where N_i denotes the number of connected spanning subgraphs with i (n-1!im) edges in G. In this paper, by proving new inequalities on the sequence N_n-1,N_n,...,N_m, we show an interesting and stronger property that the sequence γ_n-1,γ_n,...,γ_m, where γ_i denotes the average number of spanning trees in the connected spanning subgraphs with i edges, is a convex sequence as well as a monotonically increasing sequence, although this property does not hold for the sequence N_n-1,N_n,...,N_m.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e86-a_5_1027/_p

Copy

@ARTICLE{e86-a_5_1027,
author={Peng CHENG, Shigeru MASUYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Properties on the Average Number of Spanning Trees in Connected Spanning Subgraphs for an Undirected Graph},
year={2003},
volume={E86-A},
number={5},
pages={1027-1033},
abstract={Consider an undirected graph G=(V,E) with n (=|V|) vertices and m (=|E|) edges. It is well-known that the problem of computing the sequence N_n-1,N_n,...,N_m is #P-complete (see e.g.,[3]), where N_i denotes the number of connected spanning subgraphs with i (n-1!im) edges in G. In this paper, by proving new inequalities on the sequence N_n-1,N_n,...,N_m, we show an interesting and stronger property that the sequence γ_n-1,γ_n,...,γ_m, where γ_i denotes the average number of spanning trees in the connected spanning subgraphs with i edges, is a convex sequence as well as a monotonically increasing sequence, although this property does not hold for the sequence N_n-1,N_n,...,N_m.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - Properties on the Average Number of Spanning Trees in Connected Spanning Subgraphs for an Undirected Graph
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1027
EP - 1033
AU - Peng CHENG
AU - Shigeru MASUYAMA
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2003
AB - Consider an undirected graph G=(V,E) with n (=|V|) vertices and m (=|E|) edges. It is well-known that the problem of computing the sequence N_n-1,N_n,...,N_m is #P-complete (see e.g.,[3]), where N_i denotes the number of connected spanning subgraphs with i (n-1!im) edges in G. In this paper, by proving new inequalities on the sequence N_n-1,N_n,...,N_m, we show an interesting and stronger property that the sequence γ_n-1,γ_n,...,γ_m, where γ_i denotes the average number of spanning trees in the connected spanning subgraphs with i edges, is a convex sequence as well as a monotonically increasing sequence, although this property does not hold for the sequence N_n-1,N_n,...,N_m.
ER -