Generalized hypercubes and (0, 2)-graphs (Q1356767): Difference between revisions

Suppose \(S\) is a subset of the first \(d\) integers \(\{1,2,\dots,d\}\). Define the generalized hypercube \(Q_d(S)\) as follows. The vertex set is \(\{0,1\}^d\). Two vertices are joined by an edge if the distance between them in \(Q_d\) belongs to \(S\). Mulder defined a \((0,2)\)-graph to be one where any two vertices have no or exactly two common neighbors. The authors prove results about the structure of generalized hypergraphs and characterize those that are \((0,2)\)-graphs. The concluding section of the paper produces a class of \((0,2)\)-graphs that are not vertex-transitive. The existence of these graphs contradicts a conjecture of Mulder on the convexity of interval-regular graphs.