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 Multigraph
Peng CHENG Shigeru MASUYAMA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2008/02/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graphs and Networks
multigraph, the number of connected spanning subgraphs, network reliability polynomial, inequality,
Full Text: PDF(302.9KB)>>
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  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.