Geodesic
Linkedness of Cartesian products of complete graphs
Ars Mathematica Contemporanea, Tome 22 (2022) no. 2, article no. 09, 10 p.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.2577.25d
Keywords: k-linked, cyclic polytope, connectivity, dual polytope, linkedness, Cartesian product 
@article{10_26493_1855_3974_2577_25d,
     author = {Leif K. J{\o}rgensen and Guillermo Pineda-Villavicencio and Julien Ugon},
     title = {Linkedness of {Cartesian} products of complete graphs},
     journal = {Ars Mathematica Contemporanea},
     eid = {09},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2022},
     doi = {10.26493/1855-3974.2577.25d},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2577.25d/}
}
TY  - JOUR
AU  - Leif K. Jørgensen
AU  - Guillermo Pineda-Villavicencio
AU  - Julien Ugon
TI  - Linkedness of Cartesian products of complete graphs
JO  - Ars Mathematica Contemporanea
PY  - 2022
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2577.25d/
DO  - 10.26493/1855-3974.2577.25d
LA  - en
ID  - 10_26493_1855_3974_2577_25d
ER  - 
%0 Journal Article
%A Leif K. Jørgensen
%A Guillermo Pineda-Villavicencio
%A Julien Ugon
%T Linkedness of Cartesian products of complete graphs
%J Ars Mathematica Contemporanea
%D 2022
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2577.25d/
%R 10.26493/1855-3974.2577.25d
%G en
%F 10_26493_1855_3974_2577_25d
Leif K. Jørgensen; Guillermo Pineda-Villavicencio; Julien Ugon. Linkedness of Cartesian products of complete graphs. Ars Mathematica Contemporanea, Tome 22 (2022) no. 2, article  no. 09, 10 p. doi : 10.26493/1855-3974.2577.25d. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2577.25d/

Cité par Sources :