Partial cubes

This problem was submitted by Sandi Klav\v{z}ar, Department of Mathematics, PeF, University of Maribor, Koro\v ska 160, 2000 Maribor, Slovenia

sandi.klavzar@uni-lj.si

A subgraph H of a graph G is an isometric subgraph if d_H(u,v)=d_G(u,v) for all u,v\in V(H), where d_G(u,v) denotes the length of a shortest path between u and v in G. Isometric subgraphs of hypercubes are known as partial cubes.

Problem 1: What is the recognition complexity for partial cubes? In particular, can the present O(mn) complexity (n = |V(G)|, m=|E(G)|) be improved?

Problem 2: Classify regular partial cubes.

References:
F. Aurenhammer and J. Hagauer, Recognizing binary Hamming graphs in O(n^2 log n) time, Math. Systems Theory 28 (1995) 387--396.
W. Imrich and S. Klavzar, A simple O(mn) algorithm for recognizing Hamming graphs, Bull. Inst. Comb. Appl. 9 (1993) 45--56.
W. Imrich and S. Klavzar, Product Graphs: Structure and Recognition, Wiley, New York, 2000.

Back to the Problem Session page and to the workshop page