Circular clique number

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

Circular clique numberцикловое кликовое число.

The circular clique number of a graph \,G, denoted by \,\omega_{c}(G), is defined as the maximum quotient \,k/d such that the graph \,G_{d}^{k} (k \geq 2d) admits a homomorphism to \,G.

The graph G_{d}^{k} is defined as follows:

V(G_{d}^{k}) = \{v_{0}, v_{1}, \ldots, v_{k-1}\},

E(G_{d}^{k}) = \{v_{i},v_{j} : d \leq |j - i| \leq k-d \bmod k\}.

Литература

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