Wir betrachten Graphen

${\displaystyle {}G=S(n_{1},n_{2},\ldots ,n_{k})\,}$

von der folgenden Bauart: Es gibt ein Zentrum ${\displaystyle {}z}$, an das ${\displaystyle {}k}$ lineare Graphen (Strahlen) der Länge ${\displaystyle {}n_{1},n_{2},\ldots ,n_{k}}$ anliegen. Ansonsten gibt es keine weiteren Kanten.

1. Skizziere einen solchen Graphen für ${\displaystyle {}k=5}$ und

   ${\displaystyle {}(n_{1},n_{2},n_{3},n_{4},n_{5})=(2,3,1,3,4)\,.}$

2. Erstelle eine Formel für die Anzahl der Knoten und die Anzahl der Kanten von ${\displaystyle {}G}$.
3. Beschreibe eine minimale Knotenüberdeckung von ${\displaystyle {}G}$, die ${\displaystyle {}z}$ enthält, und eine minimale Knotenüberdeckung, die ${\displaystyle {}z}$ nicht enthält.
4. Bestimme die Knotenüberdeckungszahl von ${\displaystyle {}G}$.