Geodesic
The diameter of the ridge-graph of a~cyclic polytope
Diskretnaya Matematika, Tome 21 (2009) no. 2, pp. 146-152.

Voir la notice de l'article provenant de la source Math-Net.Ru

It is shown that the diameter of the the ridge-graph, that is, the graph of the polytope $C^*(d,n)$ dual to the given polytope, where $d$ is the dimension and $n$ is the number of facets of the polytope, is equal to $n-d-\max\{0,\lceil(n-2d)/(\lfloor d/2\rfloor+1)\rceil\}$. 
@article{DM_2009_21_2_a10,
     author = {A. N. Maksimenko},
     title = {The diameter of the ridge-graph of a~cyclic polytope},
     journal = {Diskretnaya Matematika},
     pages = {146--152},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2009_21_2_a10/}
}
TY  - JOUR
AU  - A. N. Maksimenko
TI  - The diameter of the ridge-graph of a~cyclic polytope
JO  - Diskretnaya Matematika
PY  - 2009
SP  - 146
EP  - 152
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2009_21_2_a10/
LA  - ru
ID  - DM_2009_21_2_a10
ER  - 
%0 Journal Article
%A A. N. Maksimenko
%T The diameter of the ridge-graph of a~cyclic polytope
%J Diskretnaya Matematika
%D 2009
%P 146-152
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2009_21_2_a10/
%G ru
%F DM_2009_21_2_a10
A. N. Maksimenko. The diameter of the ridge-graph of a~cyclic polytope. Diskretnaya Matematika, Tome 21 (2009) no. 2, pp. 146-152. http://geodesic.mathdoc.fr/item/DM_2009_21_2_a10/

[1] Brensted A., Vvedenie v teoriyu vypuklykh mnogogrannikov, Mir, Moskva, 1988 | MR

[2] Emelichev V. A., Kovalev M. M., Kravtsov M. K., Mnogogranniki, grafy, optimizatsiya, Nauka, Moskva, 1981 | MR | Zbl

[3] Altshuler A., Bokowski J., Steinberg L., “The classification of simplicial 3-spheres with nine vertices into polytopes and non-polytopes”, Discrete Math., 31 (1980), 115–124 | DOI | MR | Zbl

[4] Carathéodory C., “Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen”, Math. Ann., 64 (1907), 95–115 | DOI | MR | Zbl

[5] Dantzig G. B., Linear programming and extensions, Princeton Univ. Press, Princeton, 1963 | MR | Zbl

[6] Ferrez J.-A., Fukuda K., Liebling T. M., “Parallel implementation of graph diameter algorithms”, EPFL Supercomputing Review, 1998, no. 10, 3–6

[7] Fritzsche K., Holt F. B., “More polytopes meeting the conjectured Hirsch bound”, Discrete Math., 205 (1999), 77–84 | DOI | MR | Zbl

[8] Gale D., “Neighboring vertices on a convex polyhedron”, Ann. Math. Stud., 38 (1956), 255–264 | MR | Zbl

[9] Gale D., “Neighborly and cyclic polytopes”, Proc. Symp. Pure Math., 7 (1963), 225–232 | MR | Zbl

[10] Grünbaum B., Convex polytopes, Wiley, New York, 1967 | MR | Zbl

[11] Holt F. B., Klee V., “Many polytopes meeting the conjectured Hirsch bound”, Discrete Comput. Geom., 20 (1998), 1–17 | DOI | MR | Zbl

[12] Kalai G., “Polytope skeletons and paths”, Handbook of discrete and computational geometry, eds. Goodman J. E. et al., CRC Press, Boca Raton, FL, 1997, 331–344 | MR | Zbl

[13] Klee V., “Diameters of polyhedral graphs”, Canad. J. Math., 16 (1964), 602–614 | MR | Zbl

[14] Klee V., “Paths on polyhedra. II”, Pacific J. Math., 17 (1966), 249–262 | MR | Zbl

[15] Klee V., Walkup D. W., “The $d$-step conjecture for polyhedra of dimension $d6$”, Acta Math., 133 (1967), 53–78 | DOI | MR

[16] Lagarias J. C., Prabhu N., “Counting $d$-step paths in extremal Dantzig figures”, Discrete Comput. Geom., 19 (1998), 19–31 | DOI | MR | Zbl

[17] McMullen P., “The maximum numbers of faces of a convex polytope”, Mathematika, Lond., 17 (1970), 179–184 | MR | Zbl