Stjärngraf

Inom grafteori är en stjärngraf S_k den kompletta bipartita grafen K_1,k: ett träd med en intern nod och k blad (löv) för k>1, men utan interna noder och med k + 1 blad för k ≤ 1. Vissa författare definierar däremot S_k som trädet av ordning k med största diameter 2, i vilket fall en stjärngraf med k>2 i stället har k − 1 blad.

En stjärngraf med tre kanter kallas klograf.

En stjärngraf kan också beskrivas som en graf med högst en nod som har en högre grad än ett. En stjärngraf är en kanttransitiv tändsticksgraf, har ett kromatiskt tal som är 2 och ett kantkromatiskt tal som är k.

Prüfersekvensen för en orotad märkt stjärngraf K_1,k består av k − 1 upprepningar av centralnoden.

Stjärngraferna S₃, S₄, S₅ och S₆.