The graph of an abstract polytope
Autor: | Katta G. Murty |
---|---|
Rok vydání: | 1973 |
Předmět: |
Factor-critical graph
Discrete mathematics medicine.medical_specialty Mathematics::Combinatorics Birkhoff polytope General Mathematics Polyhedral combinatorics MathematicsofComputing_NUMERICALANALYSIS Complete graph Uniform k 21 polytope Geometric graph theory Combinatorics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Convex polytope medicine Mathematics::Metric Geometry Regular graph Software MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
Zdroj: | Mathematical Programming. 4:336-346 |
ISSN: | 1436-4646 0025-5610 |
DOI: | 10.1007/bf01584675 |
Popis: | Recently a generalization of simple convex polytopes to combinatorial entities known as abstract polytopes has been proposed. The graph of an abstract polytope of dimension d is a regular connected graph of degree d. Given a connected regular graph F of degree d, it is interesting to find out whether it is the graph of some abstract polytope P. We obtain necessary and sufficient conditions for this, in terms of the existence of a class of simple cycles in P satisfying certain properties. The main result in this paper is that if a pair of simple convex polytopes or abstract polytopes have the same two-dimensional skeleton, then they are isomorphic. Every twodimensional face of a simple convex polytope or an abstract polytope is a simple cycle in its graph. Given the graph of a simple convex polytope or an abstract polytope and the simple cycles in this graph corresponding to all its two-dimensional faces, then we show how to construct all its remaining faces. Given a regular connected graph F and a class of simple cyles D ,in it, we provide necessary and sufficient conditions under which ~is the class of two-dimensional faces of some abstract polytope which has r as its graph. |
Databáze: | OpenAIRE |
Externí odkaz: |