Suche kleine alternierende planare Graphen

[Ingo Althöfer]

Hallo allerseits,

ein planarer Graph heisst alternierend, wenn es darin

* kein Paar benachbarter Ecken/Knoten mit gleichem Grad

und

* kein Paar benachbartet Flächen mit gleicher Seitenzahl

gibt.

Der kleinste mir bekannte alternierende planare Graph hat
25 Knoten und 25 Flächen (Aussenfläche mitgezählt). Ein
Bild davon findet sich unter

http://www.althofer.de/alternating-planar-graphs.html

Es wäre (für mich) eine grosse Überraschung, wenn es
nicht kleiner als mit 25 Knoten und 25 Flächen ginge.

Ingo Althöfer

[Ingo Althöfer]

Der Schachprogrammierer Frank Schneider
hat mit Computer-Hilfe den alten Rekord
pulverisiert. Seine Lösung hat
17 Ecken und 17 Flächen.

Siehe unter

http://f23.parsimony.net/forum50826/messages/178269.htm

Immer bedenken:
Jede Fläche muss mindestens 3 Seiten haben,
und jede Ecke mindestens Grad 3.

Ingo.



Ingo Althöfer schrieb:
> ein planarer Graph heisst alternierend, wenn es darin
>
> * kein Paar benachbarter Ecken/Knoten mit gleichem Grad
>
> und
>
> * kein Paar benachbartet Flächen mit gleicher Seitenzahl
>
> gibt.
>
> Der kleinste mir bekannte alternierende planare Graph hat
> 25 Knoten und 25 Flächen (Aussenfläche mitgezählt). Ein
> Bild davon findet sich unter
>
> http://www.althofer.de/alternating-planar-graphs.html
>
> Es wäre (für mich) eine grosse Überraschung, wenn es
> nicht kleiner als mit 25 Knoten und 25 Flächen ginge.
>
> Ingo Althöfer

[Ingo Althöfer]

Zum (17,17)-Graphen von Frank Schneider
hat Jan Kristian Haugland eine sehr schön
symmetriche graphische Repräsentation gefunden.

Siehe
http://www.althofer.de/alternating-planar-graphs.html

Ausserdem hat Jan Kristian bewiesen, dass jeder
alternierende planare Graph, in dem nur die Grade
3, 4, 5 vorkommen (bei Knoten und Flächen),
genauso viele Knoten wie Flächen haben muss.

Allen ein schönes Wochenende,
Ingo.