Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-20T10:23:51.126Z Has data issue: false hasContentIssue false
  • English
  • Français

Diameters of Polyhedral Graphs

Published online by Cambridge University Press:  20 November 2018

Victor Klee
Victor Klee*
Affiliation:
University of Washington and Boeing Scientific Research Laboratories
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The distance between two vertices of a connected finite graph is the smallest number of edges forming a path that joins the two vertices, and the diameter of the graph is the largest integer which is realized as the distance between two vertices of the graph. We are concerned here with the diameters of two graphs associated with a d-dimensional convex polytope P (called henceforth a d-polytope). The graph Γ(P) of P is the 1- complex formed by the vertices and edges of P , and the polar graph II (P) of P is the 1-complex whose vertices correspond to the (d — 1)-faces of P, with two vertices joined by an edge in II (P) if and only if the corresponding (d — 1)- faces intersect in a (d — 2)-face of P. The diameters of Γ(P) and II (P) will be denoted respectively by δ(P) (called the diameter of P) and ϕ(Ps) (called the face-diameter of P ).

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 16 , 1964 , pp. 602 - 614
Copyright
Copyright © Canadian Mathematical Society 1964

References

1. Balinski, M. L., An algorithm for finding all vertices of convex polyhedral sets, J. Soc. Indust. Appl. Math., 9 (1961), 72–88.Google Scholar
2. Balinski, M. L., On the graph structure of convex polyhedra in n-space, Pacific J. Math., 11 (1961), 431–434.Google Scholar
3. Brown, Thomas A., Simple paths on convex polyhedra, Pacific J. Math., 11 (1961), 1211– 1214.Google Scholar
4. Dantzig, George B., Ten unsolved problems, Hectographed notes (Berkeley, 1962).Google Scholar
5. Gale, David, Neighborly and cyclic polytopes. Proc. Symposia Pure Math., 7, Convexity (Providence, 1963), pp. 225–232.Google Scholar
6. Gale, David, On the number of faces of a convex polytope, Can. J. Math., 16 (1964), 12–17.Google Scholar
7. Grunbaum, Branko and Motzkin, Theodore S., Longest simple paths in polyhedral graphs, J. London Math. Soc, 87 (1962), 152–160.Google Scholar
8. Grunbaum, Branko and Motzkin, Theodore S., On polyhedral graphs, Proc. Symposia Pure Math., 7, Convexity (Providence, 1963), pp. 285-290.Google Scholar
9. Klee, Victor, The number of vertices of a convex polytope; to appear in this Journal.Google Scholar
10. Menger, Karl, Zur allgemeinen Kurventheorie, Fund. Math., 10 (1926), 96–115.Google Scholar
11. Saaty, T. L., A conjecture concerning the smallest bound on the iterations in linear programming, Operations Research, 11 (1963), 151–153.Google Scholar
12. Steinitz, E. and Rademacher, H., Vorlesungen iïber die Théorie des Polyeder (Berlin, 1934).Google Scholar
13. Tait, P. G., On Listing's “Topologie,” Phil. Mag. (5), 17 (1884), 30–46 (Sci. Papers, vol. 2, pp. 85-98).Google Scholar
14. Tutte, W. T., On Hamiltonian circuits, J. London Math. Soc, 21 (1946), 98–101.Google Scholar
15. Weyl, H., Elementare Théorie der konvexen Polyeder, Comment. Math. Helv., 7 (1935), 290–306 (English translation by H. W. Kuhn in Contribution to the Theory of Games (Princeton, 1950), pp. 3-18.)Google Scholar
16. Whitney, H., Congruent graphs and the connectivity of graphs, Am. J. Math., 64 (1932), 150–168.Google Scholar