Friendship 3-hypergraphs

Lia, P. C. ; van Reesa, G. H. J. ; Seo, Stela H. ; Singhi, N. M. (2012) Friendship 3-hypergraphs Discrete Mathematics, 312 (11). pp. 1892-1899. ISSN 0012-365X

[img]
Preview
PDF - Author Version
308kB

Abstract

A friendship 3-hypergraph is a 3-hypergraph in which any 3 vertices, u, v and w, occur in pairs with a unique fourth vertex x; i.e., uvx, uwx, vwx are 3-hyperedges. Sos found friendship 3-hypergraphs coming from Steiner Triple Systems. Hartke and Vandenbussche showed that any friendship 3-hypergraph can be decomposed into sets of K3 4 's. We think of this as a set of 4-tuples and call it a friendship design. We defne a geometric friendship design to be a resolvable friendship design that can be embedded into an affine geometry. Refning the problem from friendship designs to geometric designs allows us state some more structure theorems about these geometric friendship designs and decreases the state space when searching for these designs. Hartke and Vandenbussche discovered 5 new examples of friendship designs which happen to be geometric. We fnd that there are exactly three (known) non-isomorphic geometric friendship designs on 16 vertices. We also improve the known upper and lower bounds on the number of edges in a friendship 3-hypergraph. Finally we show that no friendship 3-hypergraph exists on 11 or 12 points.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:Friendship Graph; Friendship 3-hypergraphs; Geometric Friendship Designs; Bounds; Computer Algorithm
ID Code:89782
Deposited On:30 Apr 2012 14:25
Last Modified:19 May 2016 04:14

Repository Staff Only: item control page