Linkages in Polytope Graphs

DOI10.1016/J.ENDM.2008.06.038MaRDI QIDQ5301005zbMATH OpenOpenAlexFDO

Authors Axel Werner, Ronald Frank Wotzlaw

Publication date 28 June 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0710.3726, https://depositonce.tu-berlin.de//handle/11303/7193

zbMATH Keywords

connectivitydisjoint pathspolytope graphscombinatorial structure of polytopes

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: A graph is k-linked if any k disjoint vertex-pairs can be joined by k disjoint paths. We improve a lower bound on the linkedness of polytopes slightly, which results in exact values for the minimal linkedness of 7-, 10- and 13-dimensional polytopes. We analyze in detail linkedness of polytopes on at most (6d+7)/5 vertices. In that case, a sharp lower bound on minimal linkedness is derived, and examples meeting this lower bound are constructed. These examples contain a class of examples due to Gallivan.

Recommendations

• On linkages in polytope graphs
• Links in the complex of separable graphs
• Polytopes and connected subgraphs
• The Linkage of a Graph
• Topology of equilateral polygon linkages
• LINKING SYSTEMS AND MATROID PENCILS(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)
• Linkability in iterated line graphs
• scientific article; zbMATH DE number 2091892
• Pseudotriangulations, polytopes, and how to expand linkages
• Base polyhedra and the linking property

Cites work

• scientific article; zbMATH DE number 3696001 (Why is no real title available?)
• scientific article; zbMATH DE number 665689 (Why is no real title available?)
• scientific article; zbMATH DE number 1182910 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Convex Polytopes
• Disjoint edge paths between given vertices of a convex polytope
• On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes
• On the facial structure of convex polytopes
• On the graph structure of convex polyhedra in n-space

Cited in

(12)

• LINKING IN STRAIGHT-EDGE EMBEDDINGS OF K₇
• Linkage on the infinite grid
• Linkedness of Cartesian products of complete graphs
• On linkages in polytope graphs
• Linkage for the diamond and the path with four vertices
• The linkedness of cubical polytopes: the cube
• The linkedness of cubical polytopes: beyond the cube
• Incidence graphs and unneighborly polytopes
• Embedding linkages on an integer lattice
• Topology of equilateral polygon linkages
• Disjoint edge paths between given vertices of a convex polytope
• Linkage of graphs with flows

This page was built for publication: Linkages in Polytope Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5301005)