Clique-transversal

Материал из WEGA
Версия от 10:44, 24 октября 2018; KVN (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Clique-transversalкликовая трансверсаль.

A clique-transversal of a graph [math]\displaystyle{ \,G }[/math] is a subset of vertices that meets all the cliques. A clique-independent set is a collection of pairwise vertex disjoint cliques. The clique-transversal number and clique-independence number of [math]\displaystyle{ \,G }[/math], denoted by [math]\displaystyle{ \,\tau_{c}(G) }[/math] and [math]\displaystyle{ \,\alpha_{c}(G) }[/math], are the sizes of a minimum clique-transversal and a maximum clique-independent set of [math]\displaystyle{ \,G }[/math], respectively.

It is easy to see that [math]\displaystyle{ \tau_{c}(G) \geq \alpha_{c}(G) }[/math] for any graph [math]\displaystyle{ \,G }[/math]. A graph [math]\displaystyle{ \,G }[/math] is clique-perfect if [math]\displaystyle{ \,\tau_{c}(H) = \alpha_{c}(H) }[/math] for every induced subgraph [math]\displaystyle{ \,H }[/math] of [math]\displaystyle{ \,G }[/math]. If this equality holds for the graph [math]\displaystyle{ \,G }[/math], we say that [math]\displaystyle{ \,G }[/math] is clique-good.

Литература

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