REAL

Uniquely K-r((k))-saturated Hypergraphs

Gyárfás, András and Hartke, Stephen G. and Viss, Charles (2018) Uniquely K-r((k))-saturated Hypergraphs. ELECTRONIC JOURNAL OF COMBINATORICS, 25 (4). ISSN 1097-1440

[img]
Preview
Text
1712.03208v1.pdf

Download (195kB) | Preview

Abstract

In this paper we generalize the concept of uniquely K-r-saturated graphs to hypergraphs. Let K-r((k)) denote the complete k-uniform hypergraph on r vertices. For integers k, r, n such that 2 <= k < r < n, a k-uniform hypergraph H with n vertices is uniquely K-r((k))-saturated if H does not contain K-r((k)) but adding to H any k-set that is not a hyperedge of H results in exactly one copy of K-r((k)). Among uniquely K-r((k))-saturated hypergraphs, the interesting ones are the primitive ones that do not have a dominating vertex a vertex belonging to all possible ((n-1)(k-1)) edges. Translating the concept to the complements of these hypergraphs, we obtain a natural restriction of tau-critical hypergraphs: a hypergraph H is uniquely tau-critical if for every edge e, tau(H - e) = tau(H) - 1 and H - e has a unique transversal of size tau(H) - 1. We have two constructions for primitive uniquely K-r((k))-saturated hypergraphs. One shows that for k and r where 4 <= k < r <= 2k-3, there exists such a hypergraph for every n > r. This is in contrast to the case k = 2 and r = 3 where only the Moore graphs of diameter two have this property. Our other construction keeps n - r fixed; in this case we show that for any fixed k >= 2 there can only be finitely many examples. We give a range for n where these hypergraphs exist. For n- r = 1 the range is completely determined: k +1 <= n <= (k+2)(2)/4. For larger values of n - r the upper end of our range reaches approximately half of its upper bound. The lower end depends on the chromatic number of certain Johnson graphs.

Item Type: Article
Uncontrolled Keywords: NUMBER; Mathematics, Applied; SATURATED GRAPHS;
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 12 Jan 2019 13:25
Last Modified: 12 Jan 2019 13:25
URI: http://real.mtak.hu/id/eprint/89778

Actions (login required)

Edit Item Edit Item