Просмотр кода страницы Pseudo-h-hamiltonian graph

'''Pseudo-<math>h</math>-hamiltonian graph''' --- псевдо-<math>h</math>-гамильтонов граф.

For an integer <math>h \geq 1</math>, an undirected graph <math>G = (V,E)</math> is a '''pseudo-<math>h</math>-hamiltonian graph''', if there exists a circular sequence of <math>h\cdot |V|</math>
vertices such that the following properties hold:

(1) every vertex of <math>G</math> appears precisely <math>h</math> times in the sequence,
and

(2) any two consecutive vertices in the sequence are '' adjacent'' in
<math>G</math>.

A sequence with these properties will be termed a '''pseudo-<math>h</math>-hamiltonian cycle'''. In this sense, '''pseudo-1-hamiltonian''' corresponds to the standard notion ''
hamiltonian'', and a ''' pseudo-1-hamiltonian cycle''' is just a ''hamiltonian cycle''. The ''' pseudo-hamiltonicity number''' <math>ph(G)</math> of
the graph <math>G</math> is the smallest integer <math>h \geq 1</math> for which <math>G</math> is
pseudo-<math>h</math>-hamiltonian; in case no such <math>h</math> exists, <math>ph(G) = \infty</math>.
A graph <math>G</math> with finite <math>ph(G)</math> is called ''' pseudo-hamiltonian'''.
Pseudo-<math>h</math>-hamiltonicity is a non-trivial graph property. E.g., for
every <math>h \geq 2</math>, the graph <math>G_{h}</math> that results from gluing
together <math>h</math> triangles at one of their vertices is
pseudo-<math>h</math>-hamiltonian but it is not pseudo-<math>(h-1)</math>-hamiltonian.