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
      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

      Identifiers