Zvezda (teorija grafov)

Zvezda
Zvezda S7.
Točke	n+1
Povezave	n
Premer	2
Notranji obseg	$\infty \!\,$
Kromatično število	2
Kromatični indeks	n
Značilnosti	povezavnoprehoden drevo z enotsko razdaljo dvodelen
Označba	$S_{n}\!\,$

Zvezda (oznaka S_n) je v teoriji grafov polni dvodelni graf K_1,n, drevo z enim notranjim stičiščem (centrom) in n listi. Zvezda s 3 povezavami se imenuje šapa (angleško claw). Zvezda, ki po definiciji ni drevo, je S₀.

Zvezda S_n je po povezavah elegantna pri sodem n, in neelegantna pri lihem n. Graf zvezda je povezavnoprehoden, ima enotsko razdaljo, premer 2, notranji obseg ∞, kromatično število 2 in kromatični indeks n.

Zvezde se lahko opiše tudi kot edine povezane grafe v katerih ima največ ena točka stopnjo večjo kot 1. Izjemi sta S₀, ki je prazni graf (nima povezav in zato ni povezan), in S₁, kjer imata obe točki stopnji 1. Grafi S₀, S₁ in S₂ so enaki ustreznim potem P₁, P₂ in P₃.

Glej tudi

• graf brez šap

Zunanje povezave

• Weisstein, Eric W. "Star Graph". MathWorld.