
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.

Inequalities on the Number of Connected Spanning Subgraphs in a Multigraph
Peng CHENG Shigeru MASUYAMA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E91D
No.2
pp.178186 Publication Date: 2008/02/01
Online ISSN: 17451361
DOI: 10.1093/ietisy/e91d.2.178
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science) Category: Graphs and Networks Keyword: multigraph, the number of connected spanning subgraphs, network reliability polynomial, inequality,
Full Text: PDF(302.9KB)>>
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 (mi+1)N_{i1}>_{}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 (mi+1)N_{i1}(in+2)N_{i}, and give a necessary and sufficient condition by which (mi+1)N_{i1}=(in+2)N_{i}. In particular, this means that (mi+1)N_{i1}>_{}N_{i} is not valid for all multigraphs, in general. Furthermore, we prove _{}2, which is not straightforwardly derived from (mi+1)N_{i1}(in+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}^{2}>N_{n1}N_{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}^{2}>N_{n1}N_{n+1}.

