Deakin University
Browse

File(s) under embargo

The linkedness of cubical polytopes: Beyond the cube

journal contribution
posted on 2023-12-19, 04:24 authored by HT Bui, G Pineda-Villavicencio, Julien UgonJulien Ugon
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 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 k-linked if its graph is k-linked. In a previous paper [3] we proved that every cubical d-polytope is ⌊d/2⌋-linked. Here we strengthen this result by establishing the ⌊(d+1)/2⌋-linkedness of cubical d-polytopes, for every d≠3. A graph G is 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) k-linked if its graph is (strongly) k-linked. In this paper, we also prove that every cubical d-polytope is strongly ⌊d/2⌋-linked, for every d≠3. These results are best possible for this class of polytopes.

History

Journal

Discrete Mathematics

Volume

347

Article number

113801

Pagination

113801-113801

Location

Amsterdam, The Netherlands

ISSN

0012-365X

Language

en

Issue

3

Publisher

Elsevier BV

Usage metrics

    Research Publications

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC