Deakin University
Browse

File(s) under permanent embargo

Linkedness of Cartesian products of complete graphs

Version 2 2024-06-05, 04:42
Version 1 2022-09-28, 05:27
journal contribution
posted on 2024-06-05, 04:42 authored by LK Jørgensen, G Pineda-Villavicencio, Julien UgonJulien Ugon
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 ⌊(d1 + d2)/2⌋-linked for d1, d2 ≥ 2, and this is best possible. This result is connected to graphs of simple polytopes. The Cartesian product Kd1+1 × Kd2+1 is the graph of the Cartesian product T(d1) × T(d2) of a d1-dimensional simplex T(d1) and a d2-dimensional simplex T(d2). And the polytope T(d1) × T(d2) is a simple polytope, a (d1 + d2)-dimensional polytope in which every vertex is incident to exactly d1 + d2 edges. While not every d-polytope is ⌊d/2⌋-linked, it may be conjectured that every simple d-polytope is. Our result implies the veracity of the revised conjecture for Cartesian products of two simplices.

History

Journal

Ars Mathematica Contemporanea

Volume

22

Article number

P2.09

Pagination

1-10

Location

Ljubljana, Slovenia

ISSN

1855-3966

eISSN

1855-3974

Language

English

Publication classification

C1 Refereed article in a scholarly journal

Issue

2

Publisher

University of Primorska, Faculty of Mathematics, Natural Sciences and Information Technologies