Zakázaná indukovaná cesta

Úloha číslo: 3577

Najděte všechny grafy, které neobsahují indukovanou cestu délky \(2\).

  • Řešení

    Podobně jako v předchozí úloze se lze omezit na komponenty souvislosti.

    Úplné grafy neobsahují cestu délky \(2\) neboli graf \(P_3\) indukovaně, protože každá trojice vrcholů indukuje \(K_3\) a nikoli \(P_3\).

    Jiné komponenty než úplné být nemohou. Není-li souvislý graf úplný, obsahuje dva vrcholy \(u\) a \(v\) ve vzdálenosti alespoň dva. Potom první tři vrcholy z nejkratší cesty z \(u\) do \(v\) určují indukovaný \(P_3\).

  • Odpověď

    Grafy bez indukované \(P_3\) jsou disjunktní sjednocení úplných grafů.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze