𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Generalized hypercubes and (0,2)-graphs

✍ Scribed by Jean Marie Laborde; RafaïMourad Madani

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
842 KB
Volume
165-166
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A generalized hypercube Qd(S) (S s { 1,2, . , d}) has {0, l}d as vertex set and two vertices are joined whenever their mutual distance in Qd belongs to S. These graphs have been introduced in (Berrachedi and Mollard, 1996) where the notion mainly investigated there is graph embedding, especially, in the case where the host graph is a hypercube. A simple connected graph G is a (0,2)-graph if any two vertices have 0 or exactly two common neighbors as introduced in (Mulder, 1980). We give first some results about the structure of generalized hypercubes, and then characterize those of which are (0,2)-graphs. Using similar construction as in generalized hypercubes, we exhibit a class of (0,2)-graphs which are not vertex transitive which contradicts again a conjecture of Mulder (1982) on the convexity of interval regular graphs.

📜 SIMILAR VOLUMES

Infinite median graphs, (0, 2)-graphs, a
Infinite median graphs, (0, 2)-graphs, and hypercubes
✍ Hans-J. Bandelt; Henry Martyn Mulder 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 450 KB

Hypercubes are characterized among connected bipartite graphs by interval conditions in several ways. These results are based on the following two facts: (i) connected bipartite graphs are median provided that all their intervals induce median graphs, and (ii) median (0, 2)graphs are hypercubes. No

A generalization of hypercubes: Compleme
A generalization of hypercubes: Complemented graphs
✍ J. Nieminen; M. Peltola 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 486 KB

## Communicated by A. Tucker Abstract--Complemented graphs are a direct generalization of hypercubes as well as a special class of prime convex intersection graphs. The n-tuple representation of points of a hypercube Qn is extended to prime convex intersection graphs.

Highly Fault-Tolerant Routings and Fault
Highly Fault-Tolerant Routings and Fault-Induced Diameter for Generalized Hypercube Graphs
✍ Koichi Wada; Takaharu Ikeo; Kimio Kawaguchi; Wei Chen 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 130 KB

Consider a communication network G in which a limited number of link and/or node faults F might occur. A routing ρ for the network (a fixed path between each pair of nodes) must be chosen without knowing which components might become faulty. The diameter of the surviving route graph R(G, ρ)/F, where