Vol. 25, No. 2, 1968

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 297: 1
Vol. 296: 1  2
Vol. 295: 1  2
Vol. 294: 1  2
Vol. 293: 1  2
Vol. 292: 1  2
Vol. 291: 1  2
Vol. 290: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
Author Index
To Appear
 
ISSN: 0030-8730
On the tetrahedral graph

Martin Aigner

Vol. 25 (1968), No. 2, 219–227
Abstract

Generalizing the conccpt of the triangular association scheme, Bose and Laskar introduced the tetrahedral graph the vertices of which are the (n)
3 unordered triplets selected from n symbols with two points adjacent if and only if their corresponding triplets have two symbols in common. If we let d(x,y) denote the distance between two vertices x, y and Δ(x,y) the number of vertices adjacent to both x and y, then the tetrahedral graph possesses the following 4 properties:

(B0) the number of vertices is (n)
3

(B1) it is connected and regular of degree 3(n 3)

(B2) if d(x,y) = 1 then Δ(x,y) = n 2

(B3) if d(x,y) = 2 then Δ(x,y) = 4.

The question whether these conditions characterize tetrahedral graphs (no loops or parallel edges permitted) was answered in the affirmative by Bose and Laskar for n > 16. In the present paper characterizations of tetrahedral graphs are derived by strengthening each one of (B1), (B2), (B3) and these results are utilized to prove the sufficiency of (B0)–(B3) for n = 6. (For n < 4 the problem is void, n = 4,5 are trivial cases.)

Mathematical Subject Classification
Primary: 05.40
Milestones
Received: 19 May 1967
Published: 1 May 1968
Authors
Martin Aigner