Unbalanced Spanning Subgraphs in Edge Labeled Complete Graphs
Résumé
Let K be a complete graph of order n. For d∈(0,1), let c be a ±1-edge labeling of K such that there are d(n2) edges with label +1, and let G be a spanning subgraph of K of maximum degree at most Δ and with m(G) edges. We prove the existence of an isomorphic copy G′ of G in K such that the number of edges with label +1 in G′ is at least (d+min{2−d−2√1−d,√d−d}2Δ+1−O(1n))m(G), that is, this number visibly exceeds its expected value d⋅m(G) when considering a uniformly random copy of G in K. For d=12, and Δ≤2, we present more detailed results.
Domaines
Combinatoire [math.CO]
Fichier principal
unbalanced_spanning_subgraphs_in_edge_labeled_complete_graphs.pdf (325.28 Ko)
Télécharger le fichier
Origine | Fichiers produits par l'(les) auteur(s) |
---|