ΘΘ-graceful labelings of partial cubes

Partial cubes are graphs that allow isometric embeddings into hypercubes. ΘΘ-graceful labelings of partial cubes are introduced as a natural extension of graceful labelings of trees. It is shown that several classes of partial cubes are ΘΘ-graceful, for instance even cycles, Fibonacci cubes, and (newly introduced) lexicographic subcubes. The Cartesian product of ΘΘ-graceful partial cubes is again such and we wonder whether in fact any partial cube is ΘΘ-graceful. A connection between ΘΘ-graceful labelings and representations of integers in certain number systems is established. Some directions for further investigation are also proposed.