Critical 3-hypergraphs

DOI10.1007/S00373-022-02595-8MaRDI QIDQ2108059zbMATH OpenOpenAlexFDO

Authors Abderrahim Boussaïri, Brahim Chergui, P. Ille, Mohamed Zaidi

Publication date 19 December 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.14527

zbMATH Keywords

critical graphsmodule of a hypergraphprime 3-hypergraph

Mathematics Subject Classification ID

Hypergraphs (05C65) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Given a 3-hypergraph $H$, a subset $M$ of $V(H)$ is a module of $H$ if for each $einE(H)$ such that $ecapMeqemptyset$ and $esetminusMeqemptyset$, there exists $minM$ such that $ecapM=m$ and for every $ninM$, we have $(esetminusm)cupninE(H)$. For example, $emptyset$, $V(H)$ and $v$, where $vinV(H)$, are modules of $H$, called trivial. A 3-hypergraph is prime if all its modules are trivial. Furthermore, a prime 3-hypergraph is critical if all its induced subhypergraphs, obtained by removing one vertex, are not prime. We characterize the critical 3-hypergraphs.

Review text

The authors obtain a nice characterization for critical 3-hypergraphs. They obtained several related interesting results in their previous publications in the same journal. The proof given here for their main result is very deep and long with several lemmas and the notes on notations themselves are mindboggling. The ideas are very original. To obtain the characterization they conceive the notion of a module for a hypergraph and by using the modular decomposition tree they show that a necessary and sufficient condition for a 3-hypergraph to be realizable is that all its prime-induced subhypergraphs are realizable. They also showed earlier [Discrete Math. 277, No. 1--3, 29--43 (2004; Zbl 1037.05024)] that a given realizable 3-hypergraph \(H\) is prime if and only if all its realizations are prime. This stimulated them to probe the prime and induced subhypergraphs of a prime 3-hypergraph. Their characterization gives a simple method to construct critical 3-hypergraphs that are not realizable.

Recommendations

• Prime 3-uniform hypergraphs
• 3-uniform hypergraphs: modular decomposition and realization by tournaments
• Decomposable and indecomposable critical hypergraphs
• Prime criticality and prime covering
• A note on non-reconstructible 3-hypergraphs

Cites work

• 3-uniform hypergraphs: modular decomposition and realization by tournaments
• \(P_ 4\)-trees and substitution decomposition
• Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
• Critically twin primitive 2-structures
• scientific article; zbMATH DE number 1478125 (Why is no real title available?)
• scientific article; zbMATH DE number 887768 (Why is no real title available?)
• Indecomposability graph and critical vertices of an indecomposable graph
• Indecomposable graphs
• On Convex Subsets in Tournaments
• Parity Graphs
• Prime 3-uniform hypergraphs
• The \(C_{3}\)-structure of the tournaments.

Cited in

(3)

• Prime 3-uniform hypergraphs
• Partially pair-critical digraphs
• The primality graph of critical 3-hypergraphs

This page was built for publication: Critical 3-hypergraphs

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