Generalized hypercubes and (0, 2)-graphs

DOI10.1016/S0012-365X(96)00343-3MaRDI QIDQ1356767zbMATH OpenOpenAlexFDO

Authors Rafaï Mourad Madani, Jean-Marie Laborde

Publication date 28 September 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(96)00343-3

zbMATH Keywords

conjecture of Muldergeneralized hypercubegeneralized hypergraphsinterval-regular graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Hypergraphs (05C65) Structural characterization of families of graphs (05C75)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 4208116
• On two problems about (0, 2)-graphs and interval-regular graphs
• 4-cycle properties for characterizing rectagraphs and hypercubes.
• Two characterizations of generalized hypercube
• Characterization of Laborde-Mulder graphs (extended odd graphs)

Cites work

• Characterization of Laborde-Mulder graphs (extended odd graphs)
• scientific article; zbMATH DE number 3697163 (Why is no real title available?)
• Interval-regular graphs
• Interval-regularity does not lead to interval monotonicity
• On two problems about (0, 2)-graphs and interval-regular graphs

Cited in

(7)

• Generalized octahedra and cliques in intersection graphs of uniform hypergraphs
• Characterization of Laborde-Mulder graphs (extended odd graphs)
• On two problems about (0, 2)-graphs and interval-regular graphs
• scientific article; zbMATH DE number 4208116 (Why is no real title available?)
• Automorphisms group of generalized Hamming Graphs
• Generalized hypercube graph \(\mathcal{Q}_n(S)\), graph products and self-orthogonal codes
• 4-cycle properties for characterizing rectagraphs and hypercubes.

This page was built for publication: Generalized hypercubes and (0, 2)-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356767)