Inequalities on the Number of Connected Spanning Subgraphs in a Multigraph

Peng CHENG  Shigeru MASUYAMA  

IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.2   pp.178-186
Publication Date: 2008/02/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e91-d.2.178
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)>>
Buy this Article

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.