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

    Identifiers