Bridged graph

Материал из WikiGrapp
Перейти к:навигация, поиск

Bridged graphграф с мостами.

A graph G is a bridged graph if each cycle C of length at least 4 contains two vertices whose distance from each other in G is strictly less than that in C. A graph is called bridged if every cycle of length at least 4 has a bridge. Observe that in a bridged graph every cycle of length 4 or 5 has a chord. Bridged graphs are in general not perfect, as the wheel W_{7} shows.

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.