Name
Abstract | ||
|---|---|---|
For a k-graph F, let t l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K m k denote the complete k-graph on m vertices. The function $$t_{k-1} (kn, 0, K_k^k)$$(i.e. when we want to guarantee a perfect matching) has been previously determined by Kühn and Osthus [9] (asymptotically) and by Rödl, Ruciński, and Szemerédi [13] (exactly). Here we obtain asymptotic formulae for some other l. Namely, we prove that for any $$k \ge 4$$and $$k/2 \le l \le k-2$$, $$ t_l(kn, 0, K_k^k) = \left(\frac{1}{2} + o(1)\right) {kn\choose k-l} $$is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number sdγ(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Haynes et al. (Discussiones Mathematicae Graph Theory 21 (2001) 239-253) conjectured that $${\rm sd}_{\gamma} (G) \le \delta(G) + 1$$for any graph G with $$\delta(G) \ge 2$$. In this note we first give a counterexample to this conjecture in general and then we prove it for a particular class of graphs. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s00373-008-0787-7 | Graphs and Combinatorics |
Keywords | DocType | Volume |
domination number,domination subdivision number sd,Large Codegree,K m k denote,Perfect Matchings,minimum number,K 43-Tilings,k-graph G,k-graph F,m vertex,complete k-graph,graph G,minimum cardinality | Journal | 24 |
Issue | ISSN | Citations |
4 | 0911-0119 | 16 |
PageRank | References | Authors |
1.03 | 3 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oleg Pikhurko | 1 | 318 | 47.03 |