Circular clique number

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

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

The graph [math]\displaystyle{ G_{d}^{k} }[/math] is defined as follows:

[math]\displaystyle{ V(G_{d}^{k}) = \{v_{0}, v_{1}, \ldots, v_{k-1}\} }[/math],

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

Литература

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