Extension of a clique cover result to uniform hypergraphs (Q1078579): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Graphs which, with their complements, have certain clique covering numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4101860 / rank | |||
Normal rank |
Revision as of 15:10, 17 June 2024
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
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
clique cover
0 references
r-uniform hypergraph
0 references