Indecomposable regular graphs and hypergraphs
type: Item
instance of: scholarly article
title: Indecomposable regular graphs and hypergraphs
zbMATH Open document ID: 0755.05081
DOI: 10.1016/0012-365X(92)90590-C
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: A hypergraph \(H\) consists of a finite nonempty set \(V(H)\) called the vertex set and a collection \(E(H)\) (called the edge set of \(H)\) of subsets of the power set of \(V(H)\). Note \(E(H)\) may contain the same set more then once. The number of times an element \(e\) in \(E(H)\) appears in \(E(H)\) is called its multiplicity denoted by \(m_ H(e)\). If each edge of \(H\) appears exactly once in \(E(H)\), \(H\) is said to be a simple hypergraph. A hypergraph is a \(k\)-uniform hypergraph if each edge contains \(k\) elements. The 2-uniform hypergraphs are graphs. The degree of a vertex \(v\) in \(H\) is defined by \(\deg_ H(v)=\Sigma(m_ H(e)\mid v\in e\in E(H))\). The hypergraph \(H\) is \(d\)-regular if \(\deg_ H(v)=d\) for all \(v\in V(H)\). A subhypergraph is a spanning subhypergraph if \(\cup E(F)=\cup E(H)\). The hypergraph \(H\) is indecomposable if it contains no proper non-empty regular spanning subhypergraph. It is shown that if \(d>\sqrt n-1\) and if \(G\) is a simple \(d\)-regular graph on \(n\) vertices, then \(G\) contains a proper regular spanning subhypergraph; and if \(G\) is a \(d\)-regular multigraph with \(n\) vertices such that \(d>(n-1)/3\), then \(G\) contains a proper regular spanning subgraph. It is shown that these bounds are sharp for odd \(d\). For \(n\geq k\geq 1\), \(D(n,k)\) is the maximum possible \(d\) such that there exists a \(d\)-regular indecomposable \(k\)- uniform hypergrah on \(n\) vertices. Alon and Berman conjectured that \(D(n,k)\leq n^{c(k)}\) where \(c(k)\) depends on \(k\) only. This conjecture is disproved in this paper by constructing examples that show that \(D(n,3)\geq 2^{(n-6)/2}\).
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 89890
zbMATH Keywords: regular graphs
zbMATH Keywords: decomposition
zbMATH Keywords: hypergraph
zbMATH Keywords: multiplicity
zbMATH Keywords: simple hypergraph
zbMATH Keywords: regular spanning subhypergraph
author: Zoltán Füredi
reviewed by: Ortrud R. Oellermann
MaRDI profile type: Publication
cites work: Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory
cites work: Q3941433
cites work: On the Fractional Covering Number of Hypergraphs
cites work: Q3346336
cites work: Q4063467
cites work: Q3710533
cites work: Matching theory
cites work: Julius Petersen's theory of regular graphs
cites work: Q4750685
full work available at URL: 0012-365x(92)90590-c
OpenAlex ID: W2080495191
description: scientific article; zbMATH DE number 89890