A convex characterization of the graphs of the dodecahedron and icosahedron (Q794675)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A convex characterization of the graphs of the dodecahedron and icosahedron |
scientific article |
Statements
A convex characterization of the graphs of the dodecahedron and icosahedron (English)
0 references
1984
0 references
Sei \(\Gamma\) ein ungerichteter zusammenhängender Graph. Ein Pfad minimaler Länge zwischen zwei Ecken heißt geodätisch. Ein induzierter Teilgraph heißt konvex, wenn er zu zwei seiner Punkte stets auch jeden geodätischen Pfad aus \(\Gamma\) enthält. Die Punkte, die Kanten sowie \(\Gamma\) selbst sind triviale Beispiele für konvexe induzierte Teilgraphen von \(\Gamma\). Diese heißen uneigentlich, die übrigen eigentlich. Die Autorin hat in ''A convexity problem in 3- polytopal graphs'' (eingereicht bei Arch. Math.) untersucht, für welche Polyeder der Ecken-Kanten-Graph \(\Gamma\) (P) die Eigenschaft hat, daß die Flächen konvexe Teilgraphen liefern, und daß man so alle eigentlichen konvexen Teilgraphen erhält. Von den fünf platonischen Körpern haben das Dodekaeder D und das Ikosaeder I nicht diese Eigenschaft. Zu einem Polyeder P sei C(P) die Menge der Isomorphieklassen seiner konvexen induzierten Teilgraphen. Die Autorin listet C(D) und C(I) auf (hierbei ist \(D_ 6\) falsch) und zeigt sodann: Sei P ein Polyeder, für den der Ecken-Kanten-Graph einer Fläche von P stets konvex in \(\Gamma\) (P) ist. Dann gilt: Ist \(C(P)=C(D)\), so ist \(\Gamma\) (P) isomorph zu \(\Gamma\) (D); ist \(C(P)=C(I)\), so ist \(\Gamma\) (P) isomorph zu \(\Gamma\) (I).
0 references
geodesic path
0 references
convex subgraphs
0 references
polyhedral graph
0 references
platonic solids
0 references