Asteroidal number

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

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.