Formulas for Counting the Numbers of Connected Spanning Subgraphs with at Most n+1 Edges in a Complete Graph K_n
スポンサーリンク
概要
- 論文の詳細を見る
Let Ni be the number of connected spanning subgraphs with i(n-1≤i≤m) edges in an n-vertex m-edge undirected graph G=(V,E). Although Nn-1 is computed in polynomial time by the Matrixtree theorem, whether Nn is efficiently computed for a graph G is an open problem (see e. g., [2]). On the other hand, whether N2n≥Nn-1Nn+1 for a graph G is also open as a part of log concave conjecture (see e. g., [6], [12]). In this paper, for a complete graph Kn, we give the formulas for Nn, Nn+1, by which Nn, Nn+1 are respectively computed in polvnomial time on n, and, in particular, prove N2n>(n-1)(n-2)/n(n-3)Nn-1Nn+1 as well.
- （社）電子情報通信学会の論文
- 2008-09-01
著者
-
Masuyama Shigeru
Department of Chest Medicine, School of Medicine, Chiba University
-
Cheng Peng
Faculty Of Commerce Nagoya Gakuin University
-
Masuyama Shigeru
Department Of Applied Mathematics And Physics Faculty Of Engineering Kyoto 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)