Asteroidal number

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

Asteroidal numberастероидальное число.

A set of vertices A \subseteq V of a graph \,G = (V,E) is an asteroidal set if for each a \in A the set \,A - a is contained in one component of \,G - N[a]. The asteroidal number of a graph \,G, denoted by \,an(G), is the maximum cardinality of the asteroidal set in \,G.

Graphs with asteroidal number at most two are commonly known as AT-free graphs. The class of AT-free graphs contains well-known graph classes such as interval, permutation and cocomparability graphs.


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