Zum Inhalt springen

Strahlgraph/Knotenüberdeckungszahl/Aufgabe

Aus Wikiversity

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 .