Indecomposable regular graphs and hypergraphs

DOI10.1016/0012-365X(92)90590-CMaRDI QIDQ1197014zbMATH OpenOpenAlexFDO

Publication date 16 January 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(92)90590-c

decomposition hypergraph multiplicity regular graphs regular spanning subhypergraph simple hypergraph

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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}\).

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Indecomposable regular graphs and hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1197014)