Graphs that can be isometrically embedded into the metric space 1~ are called /rgraphs. Halved cubes play an important role in the characterization of /i-graphs. We present an algorithm that recognizes halved cubes in O(n log 2 n) time. {~) 1995 Academic Press Limited.
['Wilfried Imrich', 'Sandi Klavzar', 'Aleksander Vesel']
Recognizing Halved Cubes in a Constant Time Per Edge