Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Minimal H-factors and covers

Federico, Lorenzo and Danielsson, Joel LU orcid (2023)
Abstract
Given a fixed small graph H and a larger graph G, an H-factor is a collection of vertex-disjoint subgraphs H′⊂G, each isomorphic to H, that cover the vertices of G.
If G is the complete graph Kn equipped with independent U(0,1) edge weights, what is the lowest total weight of an H-factor? This problem has previously been considered for e.g. H=K2.
We show that if H contains a cycle, then the minimum weight is sharply concentrated around some Ln=Θ(n^(1−1/d∗)) (where d∗ is the maximum 1-density of any subgraph of H). Some of our results also hold for H-covers, where the copies of H are not required to be vertex-disjoint.
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Working paper/Preprint
publication status
published
subject
keywords
Random graphs, Graph tiling, factor, cover, sharp concentration
pages
20 pages
publisher
arXiv.org
DOI
10.48550/arXiv.2302.12184
language
English
LU publication?
yes
id
26b4da5f-977f-4ace-8a76-bfa21a755588
date added to LUP
2023-03-02 14:42:08
date last changed
2025-04-04 15:20:35
@misc{26b4da5f-977f-4ace-8a76-bfa21a755588,
  abstract     = {{Given a fixed small graph H and a larger graph G, an H-factor is a collection of vertex-disjoint subgraphs H′⊂G, each isomorphic to H, that cover the vertices of G. <br/>If G is the complete graph Kn equipped with independent U(0,1) edge weights, what is the lowest total weight of an H-factor? This problem has previously been considered for e.g. H=K2. <br/>We show that if H contains a cycle, then the minimum weight is sharply concentrated around some Ln=Θ(n^(1−1/d∗)) (where d∗ is the maximum 1-density of any subgraph of H). Some of our results also hold for H-covers, where the copies of H are not required to be vertex-disjoint.}},
  author       = {{Federico, Lorenzo and Danielsson, Joel}},
  keywords     = {{Random graphs; Graph tiling; factor; cover; sharp concentration}},
  language     = {{eng}},
  month        = {{02}},
  note         = {{Preprint}},
  publisher    = {{arXiv.org}},
  title        = {{Minimal H-factors and covers}},
  url          = {{http://dx.doi.org/10.48550/arXiv.2302.12184}},
  doi          = {{10.48550/arXiv.2302.12184}},
  year         = {{2023}},
}