On the connectivity of k-clique polytopes
Please always quote using this URN: urn:nbn:de:0297-zib-11949
- In this paper, we study the neighbourlicity of the polytope $P_{k n}^2$ constituted by the $k$-cliques of the complete graph $K_n$ on $n$ vertices. We prove that this polytope is $3$-, but not $4$-neighbourly. Following a remark of Pierre Duchet, we partially generalize this result to the $k$-clique polytopes of $r$-uniform complete hypergraphs, $P_{kn}^r$. We show that the neighbourlicity of $P_{kn}^r$ is between $r$ and $2^r-1$ whenever $k\geq r+1$ and $n\geq k+r+1$. Computational results indicate that the upper bound is tight.
Author: | Rüdiger Stephan, Jean Maurras, Roumen Nedev |
---|---|
Document Type: | ZIB-Report |
Tag: | clique polytope; connectivity |
MSC-Classification: | 52-XX CONVEX AND DISCRETE GEOMETRY / 52Bxx Polytopes and polyhedra |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut | |
Date of first Publication: | 2010/12/22 |
Series (Serial Number): | ZIB-Report (10-29) |
ZIB-Reportnumber: | 10-29 |