Generalized hypercubes and (0, 2)-graphs (Q1356767)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Generalized hypercubes and (0, 2)-graphs |
scientific article |
Statements
Generalized hypercubes and (0, 2)-graphs (English)
0 references
28 September 1997
0 references
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.
0 references
generalized hypercube
0 references
generalized hypergraphs
0 references
conjecture of Mulder
0 references
interval-regular graphs
0 references