The vertex connectivity of a {0, 2}-graph equals its degree

✍ Scribed by A.E. Brouwer; H.M. Mulder

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 140 KB
• Volume: 169
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(96)00367-6

✦ Synopsis

The first author observed that nice graphs are regular and have vertex connectivity equal to the degree. The second author observed that {0,2}-graphs are nice. This note follows immediately.

A {0, 2}-graph is a connected graph such that any two distinct vertices have either 0 or 2 common neighbours. These graphs were introduced in [-2] as a generalization of hypercubes. Examples are K,, (m = 1, 2, 4), the icosahedron, the Shrikhande graph on 16 vertices, the Klein map on 24 vertices, the incidence graphs of biplanes and Cartesian products of {0, 2}-graphs. Note that {0, 2}-graphs can have a more messy structure than these examples suggest.

It is easy to see that each {0, 2}-graph is regular, and that a {0, 2}-graph of valency d has at most 2 a vertices. The hypercubes are precisely the {0, 2}-graphs attaining this maximum for the number of vertices, see [2, 3], cf. [1]. In this note we prove the following result.