No label defined (Q3748313)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3983219
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3983219 |
Statements
1984
0 references
0.8483310341835022
0 references
0.8124178051948547
0 references
0.8098562359809875
0 references
Let \(G=(X,E)\) be a graph. The total covering number of G, denoted by \(\alpha_ 2(G)\), is the minimum cardinality of \(| X'| +| E'|\) such that X'\(\subset X\), E'\(\subset E\) and for every \(x\in X\) we have either \(x\in X'\), or \(x\in e\in E'\), or \(x\in jf\in E\) such that \(f\cap X'\neq \emptyset\) and for every \(e\in E\) we have either \(e\in E'\), or \(y\in X'\), \(y\in e\), or \(e\cap f\neq \emptyset\), \(f\in E'\). \textit{P. Erdős} and \textit{A. Meir} [Discrete Math. 19, 229-233 (1977; Zbl 0374.05047)] proved inequalities on the total covering (and matching) numbers of complementary graphs. In this paper the author generalizes their results for k-uniform hypergraphs, i.e., for families of k-elements sets. One of his results is: Let \(H=(X,E)\) be a k-uniform hypergraph, \(\bar H\) its complement, \(| X| =n\). Then \[ \lceil (n-1)/k\rceil +1\leq \alpha_ 2(H)+\alpha_ 2(\bar H)\leq \lceil (k+1)n/k\rceil. \]
0 references