An Adiabatic Quantum Algorithm for Determining Gracefulness of a Graph
Sayed Mohammad Hosseini, Mahdi Davoudi Darareh, Shahrooz Janbaz, Ali Zaghian · Zeitschrift für Naturforschung A · 2017
Abstract Graph labelling is one of the noticed contexts in combinatorics and graph theory. Graceful labelling for a graphGwitheedges, is to label the vertices ofGwith 0, 1, ℒ,esuch that, if we specify to each edge the difference value between its two ends, then any of 1, 2, ℒ,eappears exactly once as an edge label. For a given graph, there are still few efficient classical algorithms that determine either it is graceful or not, even for trees – as a well-known class of graphs. In this paper, we introduce an adiabatic quantum algorithm, which for a graceful graphGfinds a graceful labelling. Also, this algorithm can determine ifGis not graceful. Numerical simulations of the algorithm reveal that its time complexity has a polynomial behaviour with the problem size up to the range of 15 qubits. A general sufficient condition for a combinatorial optimization problem to have a satisfying adiabatic solution is also derived.