For Full-Text 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 MultigraphPeng CHENG  Shigeru MASUYAMA  Publication IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.2   pp.178-186Publication Date: 2008/02/01 Online ISSN: 1745-1361 DOI: 10.1093/ietisy/e91-d.2.178 Print ISSN: 0916-8532Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)Category: Graphs and NetworksKeyword: multigraph,  the number of connected spanning subgraphs,  network reliability polynomial,  inequality,  Full Text: PDF(302.9KB)>> Buy this Article Summary:  Consider an undirected multigraph G=(V,E) with n vertices and m edges, and let Ni denote the number of connected spanning subgraphs with i(min) edges in G. Recently, we showed in [3] the validity of (m-i+1)Ni-1>Ni 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)Ni-1(i-n+2)Ni, and give a necessary and sufficient condition by which (m-i+1)Ni-1=(i-n+2)Ni. In particular, this means that (m-i+1)Ni-1>Ni is not valid for all multigraphs, in general. Furthermore, we prove 2, which is not straightforwardly derived from (m-i+1)Ni-1(i-n+2)Ni, and also introduce a necessary and sufficent condition by which =2. Moreover, we show a sufficient condition for a multigraph to have Nn2>Nn-1Nn+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 Nn2>Nn-1Nn+1.