scientific article; zbMATH DE number 3983219

From MaRDI portal
Publication:3748313





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. \]











This page was built for publication:

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