Inequalities on the Number of Connected Spanning Subgraphs in a Multigraph

Peng CHENG; Shigeru MASUYAMA

doi:10.1093/ietisy/e91-d.2.178

Inequalities on the Number of Connected Spanning Subgraphs in a Multigraph

Peng CHENG, Shigeru MASUYAMA

Full Text Views

0

Cite this

Summary :

Consider an undirected multigraph G=(V,E) with n vertices and m edges, and let N_i denote the number of connected spanning subgraphs with i(min) edges in G. Recently, we showed in [3] the validity of (m-i+1)N_i-1>N_i for a simple graph and each i(min). Note that, from this inequality, 2 is easily derived. In this paper, for a multigraph G and all i(min), we prove (m-i+1)N_i-1(i-n+2)N_i, and give a necessary and sufficient condition by which (m-i+1)N_i-1=(i-n+2)N_i. In particular, this means that (m-i+1)N_i-1>N_i is not valid for all multigraphs, in general. Furthermore, we prove 2, which is not straightforwardly derived from (m-i+1)N_i-1(i-n+2)N_i, and also introduce a necessary and sufficent condition by which =2. Moreover, we show a sufficient condition for a multigraph to have N_n²>N_n-1N_n+1. As special cases of the sufficient condition, we show that if G contains at least +1 multiple edges between some pair of vertices, or if its underlying simple graph has no cycle with length more than 4, then N_n²>N_n-1N_n+1.

Publication: IEICE TRANSACTIONS on Information Vol.E91-D No.2 pp.178-186

Publication Date: 2008/02/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e91-d.2.178

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)

Category: Graphs and Networks

Cite this

Copy

Peng CHENG, Shigeru MASUYAMA, "Inequalities on the Number of Connected Spanning Subgraphs in a Multigraph" in IEICE TRANSACTIONS on Information, vol. E91-D, no. 2, pp. 178-186, February 2008, doi: 10.1093/ietisy/e91-d.2.178.
Abstract: Consider an undirected multigraph G=(V,E) with n vertices and m edges, and let N_i denote the number of connected spanning subgraphs with i(min) edges in G. Recently, we showed in [3] the validity of (m-i+1)N_i-1>N_i for a simple graph and each i(min). Note that, from this inequality, 2 is easily derived. In this paper, for a multigraph G and all i(min), we prove (m-i+1)N_i-1(i-n+2)N_i, and give a necessary and sufficient condition by which (m-i+1)N_i-1=(i-n+2)N_i. In particular, this means that (m-i+1)N_i-1>N_i is not valid for all multigraphs, in general. Furthermore, we prove 2, which is not straightforwardly derived from (m-i+1)N_i-1(i-n+2)N_i, and also introduce a necessary and sufficent condition by which =2. Moreover, we show a sufficient condition for a multigraph to have N_n²>N_n-1N_n+1. As special cases of the sufficient condition, we show that if G contains at least +1 multiple edges between some pair of vertices, or if its underlying simple graph has no cycle with length more than 4, then N_n²>N_n-1N_n+1.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e91-d.2.178/_p

Copy

@ARTICLE{e91-d_2_178,
author={Peng CHENG, Shigeru MASUYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={Inequalities on the Number of Connected Spanning Subgraphs in a Multigraph},
year={2008},
volume={E91-D},
number={2},
pages={178-186},
abstract={Consider an undirected multigraph G=(V,E) with n vertices and m edges, and let N_i denote the number of connected spanning subgraphs with i(min) edges in G. Recently, we showed in [3] the validity of (m-i+1)N_i-1>N_i for a simple graph and each i(min). Note that, from this inequality, 2 is easily derived. In this paper, for a multigraph G and all i(min), we prove (m-i+1)N_i-1(i-n+2)N_i, and give a necessary and sufficient condition by which (m-i+1)N_i-1=(i-n+2)N_i. In particular, this means that (m-i+1)N_i-1>N_i is not valid for all multigraphs, in general. Furthermore, we prove 2, which is not straightforwardly derived from (m-i+1)N_i-1(i-n+2)N_i, and also introduce a necessary and sufficent condition by which =2. Moreover, we show a sufficient condition for a multigraph to have N_n²>N_n-1N_n+1. As special cases of the sufficient condition, we show that if G contains at least +1 multiple edges between some pair of vertices, or if its underlying simple graph has no cycle with length more than 4, then N_n²>N_n-1N_n+1.},
keywords={},
doi={10.1093/ietisy/e91-d.2.178},
ISSN={1745-1361},
month={February},}

Copy

TY - JOUR
TI - Inequalities on the Number of Connected Spanning Subgraphs in a Multigraph
T2 - IEICE TRANSACTIONS on Information
SP - 178
EP - 186
AU - Peng CHENG
AU - Shigeru MASUYAMA
PY - 2008
DO - 10.1093/ietisy/e91-d.2.178
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E91-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2008
AB - Consider an undirected multigraph G=(V,E) with n vertices and m edges, and let N_i denote the number of connected spanning subgraphs with i(min) edges in G. Recently, we showed in [3] the validity of (m-i+1)N_i-1>N_i for a simple graph and each i(min). Note that, from this inequality, 2 is easily derived. In this paper, for a multigraph G and all i(min), we prove (m-i+1)N_i-1(i-n+2)N_i, and give a necessary and sufficient condition by which (m-i+1)N_i-1=(i-n+2)N_i. In particular, this means that (m-i+1)N_i-1>N_i is not valid for all multigraphs, in general. Furthermore, we prove 2, which is not straightforwardly derived from (m-i+1)N_i-1(i-n+2)N_i, and also introduce a necessary and sufficent condition by which =2. Moreover, we show a sufficient condition for a multigraph to have N_n²>N_n-1N_n+1. As special cases of the sufficient condition, we show that if G contains at least +1 multiple edges between some pair of vertices, or if its underlying simple graph has no cycle with length more than 4, then N_n²>N_n-1N_n+1.
ER -