Clique-transversal

Материал из WikiGrapp
Версия от 12:03, 11 ноября 2013; KEV (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

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

A clique-transversal of a graph \,G 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 \,G, denoted by \,\tau_{c}(G) and \,\alpha_{c}(G), are the sizes of a minimum clique-transversal and a maximum clique-independent set of \,G, respectively.

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

Литература

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