The linkedness of cubical polytopes: beyond the cube

DOI10.1016/J.DISC.2023.113801MaRDI QIDQ6177409zbMATH OpenOpenAlexFDO

Authors

Publication date 17 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

\(k\)-linkedconnectivitycubecubical polytopelinkednessseparator

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Abstract: A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. The paper is concerned with the linkedness of the graphs of cubical polytopes. A graph with at least $2k$ vertices is extit{$k$-linked} if, for every set of $k$ disjoint pairs of vertices, there are $k$ vertex-disjoint paths joining the vertices in the pairs. We say that a polytope is extit{$k$-linked} if its graph is $k$-linked. In a previous paper cite{BuiPinUgo20a} we proved that every cubical $d$-polytope is $floord/2$-linked. Here we strengthen this result by establishing the $floor(d+1)/2$-linkedness of cubical $d$-polytopes, for every $de3$. A graph $G$ is {it strongly $k$-linked} if it has at least $2k+1$ vertices and, for every vertex $v$ of $G$, the subgraph $G-v$ is $k$-linked. We say that a polytope is (strongly) extit{$k$-linked} if its graph is (strongly) $k$-linked. In this paper, we also prove that every cubical $d$-polytope is strongly $floord/2$-linked, for every $de3$. These results are best possible for this class of polytopes.

Recommendations

• The linkedness of cubical polytopes: the cube
• On linkages in polytope graphs
• Linkages in Polytope Graphs
• Connectivity of cubical polytopes
• Linkedness of Cartesian products of complete graphs

Cites work

• An improved linear edge bound for graph linkages
• Disjoint edge paths between given vertices of a convex polytope
• Graph minors. XIII: The disjoint paths problem
• Graph theory
• Highly linked graphs
• Incidence graphs and unneighborly polytopes
• Incidence graphs of convex polytopes
• Lectures on Polytopes
• On linkages in polytope graphs
• On Sufficient Degree Conditions for a Graph to be k-linked
• On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes
• Polytopality and Cartesian products of graphs
• The linkedness of cubical polytopes: the cube

This page was built for publication: The linkedness of cubical polytopes: beyond the cube

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