✦ LIBER ✦

Complete subgraphs of the graphs of convex polytopes

✍ Scribed by S. Gallivan; E.R. Lockeberg; P. McMullen

Publisher: Elsevier Science
Year: 1981
Tongue: English
Weight: 631 KB
Volume: 34
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(81)90019-4

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that if three vertices of the graph c?(l)) of a convex 3-polytope P are chosen, then G(P) contains a refinement of the complete graph C,, on four vertices, for which the three chosen vertices are principal (that is, correspond to vertices of C, in the refinement.. In general, all four vertices may not be preassigned as principal. For dimensiorls d 24, simple (simplicial) d-polytopes are constructed whcrre graphs contain sets of three (four) vertices, which cannot all be principal in any refinement of Cd+,.

📜 SIMILAR VOLUMES

Characterization of the cartesian produc

Characterization of the cartesian product of complete graphs by convex subgraphs

✍ Yoshimi Egawa 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 115 KB

We show that if G is a connected graph with the same proper convex subgraphs as (Kn)', the Cartesian product of r copies of Kn, r >t 2, n >t 3, then [V(G)I ~> n" with equality if and only if G is isomorphic to (Kn)'. In this note we consider only connected finite undirected simple graphs. The compl

On complete subgraphs of color-critical

On complete subgraphs of color-critical graphs

✍ Xiang-Ying Su 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 488 KB

A graph G is called k-critical if x(G) = k and x(G -e) -C x(G) for each edge e of G, where x denotes the chromatic number. T. Gallai conjectured that every k-critical graph of order n contains at most n complete (kl)-subgraphs. In 1987, Stiebitz proved Gallai's conjecture in the case k = 4, and in 1

On complete subgraphs of r-chromatic gra

On complete subgraphs of r-chromatic graphs

✍ B. Bollobás; P. Erdös; E. Szemerédi 📂 Article 📅 1975 🏛 Elsevier Science 🌐 English ⚖ 518 KB

Heights of convex polytopes

✍ Victor Klee 📂 Article 📅 1965 🏛 Elsevier Science 🌐 English ⚖ 663 KB

On the diameter of convex polytopes

✍ Peter Kleinschmidt; Shmuel Onn 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 171 KB

Edge-coloured complete graphs: Connected

Edge-coloured complete graphs: Connectedness of some subgraphs

✍ Adam Idzik; Jan Komar; Marcin Malawski 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 435 KB

If the edges of a complete graph K,., m/> 4, are painted two colours so that monochromatic K " graphs are connected, then there exists an increasing sequence ( n)n~4 of complete subgraphs whose monochromatic subgraphs are also connected. For more than two colours this is not true, but an analogous f