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

Στην θεωρία γράφων, ο αστεροειδής γράφος  είναι ο μη-κατευθυνόμενος γράφος που αποτελείται από  κόμβους , όπου οι  συνδέονται μόνο με τον , δηλαδή το σύνολο των ακμών του είναι .

Ο αστεροειδής γράφος ταυτίζεται με τον πλήρη διμερή γράφο  και με ένα δέντρο όπου η ρίζα έχει  παιδιά.

 Παραδείγματα 

 Ιδιότητες 

 Ο  έχει ακτίνα  και διάμετρο , καθώς ο κεντρικός κόμβος έχει εκκεντρότητα  και όλοι οι άλλοι έχουν εκκεντρότητα  (όταν ).

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

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

 Παραπομπές 

Κατηγορία:Θεωρία γράφων