Linkages in Polytope Graphs

DOI10.1016/J.ENDM.2008.06.038zbMATH Open1267.05103arXiv0710.3726OpenAlexW2766225017MaRDI QIDQ5301005FDOQ5301005

Ronald Frank Wotzlaw, Axel Werner

Publication date: 28 June 2013

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

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.

Full work available at URL: https://arxiv.org/abs/0710.3726

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

zbMATH Keywords

connectivitydisjoint pathspolytope graphscombinatorial structure of polytopes

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Convex Polytopes
• Title not available (Why is that?)
• On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes
• Title not available (Why is that?)
• On the graph structure of convex polyhedra in \(n\)-space
• Title not available (Why is that?)
• On the facial structure of convex polytopes
• Disjoint edge paths between given vertices of a convex polytope

Cited In (6)

• LINKING IN STRAIGHT-EDGE EMBEDDINGS OF K₇
• Linkage on the infinite grid
• Linkage for the diamond and the path with four vertices
• Embedding linkages on an integer lattice
• Topology of equilateral polygon linkages
• Disjoint edge paths between given vertices of a convex polytope

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)