Inequalities on the Number of Connected Spanning Subgraphs in a Multigraph

スポンサーリンク

概要

• 論文の詳細を見る

• 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 N2n>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 N2n>Nn-1Nn+1.

• （社）電子情報通信学会の論文
• 2008-02-01

著者

• Cheng Peng

  The Faculty Of Commerce Nagoya Gakuin University

• Masuyama Shigeru

  The Department Of Knowledge-based Information Engineering Toyohashi University Of Technology

関連論文

• A LOWER BOUND OF THE EXPECTED MAXIMUM NUMBER OF VERTEX-DISJOINT s-t PATHS ON PROBABILISTIC GRAPHS
• Computing the Expected Maximum Number of Vertex-Disjoint s-t Paths in a Probabilistic Basically Series-Parallel Digraph
• Inequalities on the Number of Connected Spanning Subgraphs in a Multigraph
• What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? : Using Outerplanar Graphs, Trapezoid Graphs and In-Tournament Graphs as Examples(Special Issue on Algorithm Engineering : Surveys)
• An Algorithm for Finding Two Edge-Disjoint Paths in Tournaments
• Parallel Algorithms for Finding a Hamiltonian Path and a Hamiltonian Cycle in an In-Tournament Graph(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク