Connectivity of cubical polytopes
- Authors: Bui, Hoa , Pineda-Villavicencio, Guillermo , Ugon, Julien
- Date: 2019
- Type: Text , Journal article
- Relation: Journal of Combinatorial Theory Series A Vol. 169, no. (Jan 2019), p. 21
- Full Text:
- Reviewed:
- Description: A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. We deal with the connectivity of the graphs of cubical polytopes. We first establish that, for any d >= 3, the graph of a cubical d-polytope with minimum degree 5 is min{delta, 2d - 2}-connected. Second, we show, for any d >= 4, that every minimum separator of cardinality at most 2d - 3 in such a graph consists of all the neighbours of some vertex and that removing the vertices of the separator from the graph leaves exactly two components, with one of them being the vertex itself. (C) 2019 Elsevier Inc. All rights reserved.
Linkedness of cartesian products of complete graphs
- Authors: Jorgensen, Leif , Pineda-Villavicencio, Guillermo , Ugon, Julien
- Date: 2022
- Type: Text , Journal article
- Relation: Ars Mathematica Contemporanea Vol. 22, no. 2 (2022), p.
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: This paper is concerned with the linkedness of Cartesian products of complete graphs. A graph with at least 2k vertices is k-linked if, for every set of 2k distinct vertices organised in arbitrary k pairs of vertices, there are k vertex-disjoint paths joining the vertices in the pairs. We show that the Cartesian product Kd1+1 × Kd2+1 of complete graphs Kd1+1 and Kd2+1 is
The linkedness of cubical polytopes : beyond the cube
- Authors: Bui, Hoa , Pineda-Villavicencio, Guillermo , Ugon, Julien
- Date: 2024
- Type: Text , Journal article
- Relation: Discrete Mathematics Vol. 347, no. 3 (2024), p.
- Relation: https://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: 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.
- Description: 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