Properties on the Average Number of Spanning Trees in Connected Spanning Subgraphs for an Undirected Graph
スポンサーリンク
概要
- 論文の詳細を見る
Consider an undirected graph G = (V,E) with n (= |V|) vertices and m (= |E|) edges. It is well-known that, the problem of computing the sequence N_<n-1>,N_n,...,N_m is #P-complete (see e.g., [3]), where N_i denotes the number of connected spanning subgraphs with i (n - 1 ≦ i ≦ m) edges in G. In this paper, by proving new inequalities on the sequence N_<n-1>,N_n,...,N_m, we show an interesting and stronger property that the sequence v_<n-1>,v_n,...,v_m, where v_i denotes the average number of spanning trees in the connected spanning subgraphs with i edges, is a convex sequence as well as a monotonically in-creasing sequence, although this property does not hold for the sequence N_<n-1>,N_n,...,N_m.
- 社団法人電子情報通信学会の論文
- 2003-05-01
著者
-
Masuyama Shigeru
Department of Chest Medicine, School of Medicine, Chiba University
-
Cheng Peng
Faculty Of Commerce Nagoya Gakuin University
-
Masuyama Shigeru
Department Of Knowledge-based Information Engineering Toyohashi University Of Technology
-
Masuyama Shigeru
Department Of Applied Mathematics And Physics Faculty Of Engineering Kyoto University
-
CHENG Peng
Faculty of Commerce, Nagoya Gakuin University
関連論文
- A New Aspect of the Carotid Body Function Controlling Hypoxic Ventilatory Decline in Humans
- An Optimal Parallel Algorithm for Constructing a Spanning Forest on Trapezoid Graphs
- An Optimal Parallel Algorithm for Finding All Hinge Vertices of a Circular-Arc Graph
- Cause Information Extraction from Financial Articles Concerning Business Performance
- Control of Upper Airway Function in Response to Hypoxia in Patients with Obstructive Sleep Apnea Syndrome
- Compensatory Excretion of Prostacyclin and Thromboxane Metabolites in Obstructive Sleep Apnea Syndrome
- The Effect of Changing Rate of PIO_2 Fall on Relationship between Ventilatory and Heart Rate Response to Progressive Hypoxia
- Analysis of Heart Rate Profile during Obstructive Sleep Apnea
- Properties on the Average Number of Spanning Trees in Connected Spanning Subgraphs for an Undirected Graph
- Formulas for Counting the Numbers of Connected Spanning Subgraphs with at Most n+1 Edges in a Complete Graph K_n
- PROPASAL OF THE UNRESTRICTED LR(k) GRAMMAR AND ITS PARSER
- A Polynomial Time Algorithm for Obtaining a Minimum Vertex Ranking Spanning Tree in Outerplanar Graphs(Invited Papers from New Horizons in Computing)
- An Informative DOM Subtree Identification Method from Web Pages in Unfamiliar Web Sites
- Formulation of Mobile Agent Allocation and Its Strong NP-Completeness(Complexity Theory)
- Multiple Document Summarization System GOLD(Special Issue on Text Processing for Information Access)
- UGLR Parser for Phrase Structure Languages as an Extension of GLR Parser (Special Section on Discrete Mathematics and Its Applications)
- T1 MINIMUM VERTEX RANKING SPANNING TREE PROBLEM : A TUTORIAL(Tutorial speech)
- A Parallel Algorithm for Finding All Hinge Vertices of an Interval Graph
- A Statistical Method for Acquiring Knowledge about the Abbreviation Possibility of Some of Multiple Adnominal Phrases(Special Issue on Text Processing for Information Access)
- A Simple Near Optimal Parallel Algorithm for Recognizing Outerplanar Graphs
- An Algorithm for Solving the Minimum Vertex Ranking Spanning Tree Problem on Interval Graphs
- MINIMUM DELAY SEMIJOIN SCHEDULES FOR LOCAL AREA DISTRIBUTED DATABASE SYSTEMS(Mathematical Theories on Computing Schemes and Their Applications)
- Assigning Polarity to Causal Information in Financial Articles on Business Performance of Companies
- An Optimal Parallel Algorithm for Constructing a Spanning Tree on Circular Permutation Graphs
- On the Largest Common Subgraph Problem
- An Algorithm for Minimum Feedback Vertex Set Problem on a Trapezoid Graph
- Automatic Construction of Train Arrival and Departure Schedules at Terminal Stations
- Linear Time Algorithms for Finding Articulation and Hinge Vertices of Circular Permutation Graphs
- A Linear-Time Algorithm for Constructing a Spanning Tree on Circular Trapezoid Graphs
- 4A3 AN ONLINE SCHEDULING ALGORITHM THAT MINIMIZES THE TOTAL COMPLETION TIME IN AN AGV SYSTEM AND ITS COMPETITIVE ANALYSIS(Technical session 4A: Material handling system)
- 5A2 AUTOMATIC CONSTRUCTION OF TRAIN ARRIVAL AND DEPARTURE SCHEDULES IN TERMINAL STATIONS(Technical session 5A: OS4: Railway scheduling)