On graphs like hypercubes. (English) Zbl 1171.05013

Nieminen, Juhani; Peltola, Matti; Ruotsalainen, Pasi

Tsukuba J. Math. 32, No. 1, 37-48 (2008).

Summary: By defining new concepts like pseudocomplements in graphs a new class of graphs is obtained. They have very many properties in common with hypercubes and therefore they are called pseudocubes. Pseudocubes are Hasse diagram graphs (covering garphs) of finite lattices, where pseucomplements constitute a sublattice. As an application, the routing and fault tolerance properties of certain pseudocubes are determined.

MSC:

05C12	Distance in graphs
05C62	Graph representations (geometric and intersection representations, etc.)
06D15	Pseudocomplemented lattices

Keywords:

hypercubes; complements; pseudocomplements; fin ite lattices; prime convex intersection; fault-tolerance; shortest path routing