Αστεροειδής γράφος

Στην θεωρία γράφων, ο αστεροειδής γράφος $S_n$ είναι ο μη-κατευθυνόμενος γράφος που αποτελείται από $n+1$ κόμβους $V=\{v_1,\dots ,v_{n+1}\}$, όπου οι $v_1,\dots ,v_n$ συνδέονται μόνο με τον $v_{n+1}$, δηλαδή το σύνολο των ακμών του είναι $E=\{\{v_1,v_{n+1}\},\{v_2,v_{n+1}\},\dots ,\{v_n,v_{n+1}\}\}$.Πρότυπο:Rp

Ο αστεροειδής γράφος ταυτίζεται με τον πλήρη διμερή γράφο $K_{1,n}$ και με ένα δέντρο όπου η ρίζα έχει $n-1$ παιδιά.

Ιδιότητες

• Ο $S_n$ έχει ακτίνα $1$ και διάμετρο $2$, καθώς ο κεντρικός κόμβος έχει εκκεντρότητα $1$ και όλοι οι άλλοι έχουν εκκεντρότητα $2$ (όταν $n>2$).

• Ο χρωματικός αριθμός του $S_n$ είναι $2$ και το χρωματικό πολυώνυμο του είναι

$P(G,x)=x\cdot (x-1{)}^{n-1}$.

Χρωματισμός αστροειδούς γράφου με δύο χρώματα.

Δείτε επίσης

• Πλήρης διμερής γράφος
• Δέντρο (θεωρία γράφων)