Copyright © 2008 The Institute of Electronics, Information and Communication Engineers
Special Section on Foundations of Computer Science -- Papers -- Graphs and Networks |
Inequalities on the Number of Connected Spanning Subgraphs in a Multigraph
1 The author is with the Faculty of Commerce, Nagoya Gakuin University, Nagoya-shi, 456–8612 Japan. E-mail: cheng{at}ngu.ac.jp, 2 The author is with the Department of Knowledge-Based Information Engineering, Toyohashi University of Technology, Toyohashi-shi, 441–8580 Japan.
 |
Abstract |
|---|
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(m 
i n) edges in G. Recently, we showed in [3] the validity of (m – i + 1)Ni–1 > (i–n + 
3+
9+8(i–n)/2
)Ni for a simple graph and each i(m i n). Note that, from this inequality, (m–n)Nn/2Nn+1 + Nn/(m–n+1)Nn–1 2 is easily derived. In this paper, for a multigraph G and all i(m i n), 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 > (i–n + 3+9+8(i–n)/2)Ni is not valid for all multigraphs, in general. Furthermore, we prove (m–n)Nn/2Nn+1 + Nn/(m–n+1)Nn–1 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 (m–n)Nn/2Nn+1 + Nn(m – n + 1)Nn–1 = 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 
2/3(m–n)
+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.
Key Words: multigraph, the number of connected spanning subgraphs, network reliability polynomial, inequality
Manuscript received April 2, 2007. Manuscript revised July 2, 2007.