Extension of a clique cover result to uniform hypergraphs (Q1078579)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Extension of a clique cover result to uniform hypergraphs
scientific article

    Statements

    Extension of a clique cover result to uniform hypergraphs (English)
    0 references
    0 references
    0 references
    0 references
    1986
    0 references
    H\(=(V,E)\) is an r-uniform hypergraph if each edge of E is composed of r nodes of V. H is complete if it has all possible \(\left( \begin{matrix} p\\ r\end{matrix} \right)\) edges and is empty if it has no edges. The complement of H is the r-uniform hypergraph \(\bar H\) whose edge set is composed of those edges not in E. A clique in H is an isolated node or a maximal complete subhypergraph. \(\theta_ 0(H)[\theta_ 2(H)]\) is the minimum number of cliques which include all nodes [all nodes and edges] of H. A node of H is unicliqual if it is in exactly one clique of H. \textit{R. C. Brigham} and \textit{R. D. Dutton} [Discrete Math. 34, 1-7 (1981; Zbl 0472.05054)] characterized graphs \((r=2)\) for which both \(\theta_ 0(H)=\theta_ 2(H)\) and \(\theta_ 0(\bar H)=\theta_ 2(\bar H)\) hold. This note similarly characterizes r-uniform hypergraphs for \(r\geq 3\) as follows: \(\theta_ 0(H)=\theta_ 2(H)\) and \(\theta_ 0(\bar H)=\theta_ 2(\bar H)\) if and only if either (a) H is complete or empty or (b) \(r=3\) and H has \(\theta_ 0(H)\) unicliqual nodes and \(\theta_ 0(\bar H)\) other nodes which form a clique with each of the unicliqual nodes.
    0 references
    0 references
    clique cover
    0 references
    r-uniform hypergraph
    0 references