Please use this identifier to cite or link to this item:
Main Title: On linkages in polytope graphs
Author(s): Werner, Axel
Wotzlaw, Ronald F.
Type: Article
Language Code: en
Abstract: A graph is k-linked if any k disjoint vertex-pairs can be joined by k disjoint paths. We slightly improve a lower bound on the linkedness of polytopes. This results in exact values for the minimal linkedness of 7-, 10- and 13-dimensional polytopes.
We analyze in detail linkedness of d-polytopes on at most (6d + 7)/5 vertices. In that case, a tight 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.
Issue Date: 2011
Date Available: 28-Nov-2017
DDC Class: 510 Mathematik
Sponsor/Funder: DFG, GRK 1408, Methoden für diskrete Strukturen
Journal Title: Advances in geometry
Publisher: De Gruyter
Publisher Place: Berlin [u.a.]
Volume: 11
Issue: 3
Publisher DOI: 10.1515/advgeom.2011.015
Page Start: 411
Page End: 427
EISSN: 1615-7168
ISSN: 1615-715X
Notes: Dieser Beitrag ist mit Zustimmung des Rechteinhabers aufgrund einer (DFG geförderten) Allianz- bzw. Nationallizenz frei zugänglich.
This publication is with permission of the rights owner freely accessible due to an Alliance licence and a national licence (funded by the DFG, German Research Foundation) respectively.
Appears in Collections:FG Kombinatorische Optimierung und Graphenalgorithmen » Publications

Files in This Item:
File Description SizeFormat 
advgeom.2011.015.pdf184.03 kBAdobe PDFThumbnail

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.