Hamiltonicity and circular distance two labellings (Q5937459): Difference between revisions

A \(k\)-circular distance two labelling of a graph \(G\) is a vertex-labelling such that the circular difference \(\pmod k\) of the labels is at least two for adjacent vertices, and at least one for vertices at distance two. Given \(G\), denote \(\sigma(G)\) the minimum \(k\) for which there exists a \(k\)-circular distance two labelling of \(G\). For a graph \(G\) on \(n\) vertices let \(G^C\) denote the complement of \(G\) and let \(p(G)\) be the path covering number of \(G\). The main result of the paper states that \(\sigma(G)\leq n\) if \(G^C\) is Hamiltonian; and \(\sigma(G)=n+p(G)\) otherwise. Furthermore, the exact value of \(\sigma(G)\) is given for \(G\) being a cycle \(C_n\) on \(n\) vertices, \(n\geq 3\), or a Cartesian product \(K_m \times K_n\), \(m\geq 2\), \(n\geq 2\) of the complete graphs \(K_m\) and \(K_n\), and for \(G\) being a graph of diameter two with a complement being Hamiltonian.