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.
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.
Reference
[1] F.T. Boesch, A. Satyanarayana, and C.L. Suffel, "Least reliable networks and the reliability domination," IEEE Trans. Commun., vol.38, no.11, pp.2004–2009, 1990. [2] M. Chari and C.J. Colbourn, "Reliability polynomials: A survey," J. Combin. Inform. System Sci., vol.22, pp.177–193, 1997. [3] P. Cheng and S. Masuyama, "Properties on the average number of spanning trees in connected spanning subgraphs for an undirected graph," IEICE Trans. Fundamentals, vol.E86-A, no.5, pp.1027–1033, May 2003. [4] P. Cheng and S. Masuyama, "Properties on the number of connected spanning subgraphs in an undirected graph," Proc. 3rd Hungarian-Japanese Symposium Discrete Mathematics and Its Applications, pp.262–268, Jan. 2003. [5] C.J. Colbourn, The Combinatorics of Network Reliability, Oxford University Press, Oxford, 1987. [6] C.J. Colbourn, "Some open problems on reliability polynomials," DIMACS Technical Report 93-28, April 1993. [7] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969. [8] J. Oxley and D. Welsh, "Chromatic, flow, and reliability polynomials: The complexity of their coefficients," Combin. Probab. Comput., vol.11, pp.403–426, 2002. [9] J.S. Provan, "The complexity of reliability computations in planar and acyclic graphs," SIAM J. Comput., vol.15, pp.694–702, 1986. [10] J.S. Provan and M.O. Ball, "The complexity of counting cuts and computing the reliability that a graph is connected," SIAM J. Comput., vol.12, pp.777–888, 1983.
CiteULike 
Connotea 
Del.icio.us What's this?
This Article 
Abstract
Full Text (PDF)
Alert me when this article is cited
Alert me if a correction is posted
Services
Email this article to a friend
Similar articles in this journal
Alert me to new issues of the journal
Add to My Personal Archive
Download to citation manager
Request Permissions
Google Scholar
Articles by CHENG, P.
Articles by MASUYAMA, S.
Search for Related Content
Social Bookmarking
What's this?