Characterization of Laborde-Mulder graphs (extended odd graphs)
type: Item
instance of: scholarly article
title: Characterization of Laborde-Mulder graphs (extended odd graphs)
zbMATH Open document ID: 0851.05046
DOI: 10.1016/0012-365X(95)00194-2
published in: Discrete Mathematics
publication date: 1996-07-02T00:00:00Z
review text: A graph is \((0, 2)\) if any two vertices have either 0 or 2 neighbors in common. The Laborde-Mulder graph \(E_k\) consists of all subsets of a \(2k- 1\)-element set of cardinality at most \(k- 1\), with an edge between such when they differ by either exactly 1 or \(2k- 2\) elements. This paper proves that any \((0, 2)\)-graph of degree \(d\) on \(2^{d- 1}\) vertices has diameter at least \(\lfloor d/2\rfloor\), with equality for odd \(d\) iff it is a Laborde-Mulder graph.
reviewed by: Frank Plastria
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 896006
zbMATH Keywords: diameter
zbMATH Keywords: Laborde-Mulder graph
author: Rafaï Mourad Madani
MaRDI profile type: Publication
cites work: Combinatorial Relations and Chromatic Graphs
cites work: Q4189321
cites work: Another characterization of hypercubes
cites work: Q3356336
cites work: Le Nombre D'Absorption Du n–Cube
cites work: Q3890733
cites work: Interval-regular graphs
cites work: On the chromatic number of cube-like graphs
cites work: The chromatic number of extended odd graphs is four
cites work: Q3995122
description: scientific article; zbMATH DE number 896006