Characterization of Laborde-Mulder graphs (extended odd graphs) (Q1916118): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q1356766 |
Changed an Item |
||
Property / author | |||
Property / author: Rafaï Mourad Madani / rank | |||
Normal rank |
Revision as of 15:32, 28 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Characterization of Laborde-Mulder graphs (extended odd graphs) |
scientific article |
Statements
Characterization of Laborde-Mulder graphs (extended odd graphs) (English)
0 references
2 July 1996
0 references
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.
0 references
diameter
0 references
Laborde-Mulder graph
0 references