Edge-Critical Isometric Subgraphs of Hypercubes

Abstract

Isometric subgraphs of hypercubes are known as partial cubes. Edge-critical partial cubes are introduced as the partial cubes \(G\) for which \(G – e\) is not a partial cube for any edge \(e\) of \(G\). An expansion theorem is proved by means of which one can generate many edge-critical partial cubes. Edge-critical partial cubes are characterized among the Cartesian product graphs. We also show that the \(3\)-cube and the subdivision graph of \(K_4\) are the only edge-critical partial cubes on at most \(10\) vertices.