
Let \(f(n,t,k)\) be the largest minimum degree of a graph on \(n\) vertices which has no system of \(K_t\)-subgraphs covering every vertex at least once but at most \(k\) times. It is shown that if \(t\geq 3\), \(k\geq 2\), \(n\geq 6t^2-4t\), \(n=q\bigl[(t-1)k+1\bigr]+r\) (here \(1\leq r\leq (t-1)k+1\)), then \(f(n,t,k)\) is either \(n-qk-\lceil {r \over t-1}\rceil\) or one bigger. Also, for \(n\geq 6\), \(k\geq (n-1)/2\), \(f(n,3,k)=\lceil {n\over 2}\rceil\) holds. If \(H\) is a graph with \(\chi(H)\geq 4\), and there is a vertex \(u\) such that \(\chi(H-\{u\})<\chi(H)\) and if \(G\) is a graph on \(n\geq n_0(\varepsilon)\) vertices with minimum degree at least \((1-{1\over {\chi(H)-1}}+\varepsilon)n\) then \(G\) can be vertex covered with edge disjoint copies of \(H\). The threshold function for the existence of a vertex cover with edge disjoint \(K_t\)'s with every vertex covered at most twice is calculated. This two hitting times (minimal number of edges for it, and that every vertex be in some \(K_t\)) are shown to be almost surely equal.
Extremal problems in graph theory, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Random graphs (graph-theoretic aspects), extremal graph theory, covering, random graphs
Extremal problems in graph theory, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Random graphs (graph-theoretic aspects), extremal graph theory, covering, random graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
