Strahlgraph/Knotenüberdeckungszahl/Aufgabe

Aus Wikiversity
Zur Navigation springen Zur Suche springen
BaummitArmen1.png

Wir betrachten Graphen

von der folgenden Bauart: Es gibt ein Zentrum , an das lineare Graphen (Strahlen) der Länge anliegen. Ansonsten gibt es keine weiteren Kanten.

  1. Skizziere einen solchen Graphen für und
  2. Erstelle eine Formel für die Anzahl der Knoten und die Anzahl der Kanten von .
  3. Beschreibe eine minimale Knotenüberdeckung von , die enthält, und eine minimale Knotenüberdeckung, die nicht enthält.
  4. Bestimme die Knotenüberdeckungszahl von .