Unbalanced Spanning Subgraphs in Edge Labeled Complete Graphs - Inria - Institut national de recherche en sciences et technologies du numérique
Loading [MathJax]/jax/output/HTML-CSS/jax.js
Article Dans Une Revue The Electronic Journal of Combinatorics Année : 2023

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{2d21d,dd}2Δ+1O(1n))m(G), that is, this number visibly exceeds its expected value dm(G) when considering a uniformly random copy of G in K. For d=12, and Δ2, we present more detailed results.
Fichier principal
Vignette du fichier
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)

Dates et versions

hal-04172966 , version 1 (28-07-2023)

Identifiants

Citer

Stéphane Bessy, Johannes Pardey, Lucas Picasarri-Arrieta, Dieter Rautenbach. Unbalanced Spanning Subgraphs in Edge Labeled Complete Graphs. The Electronic Journal of Combinatorics, 2023, 30 (1), pp.1-35. ⟨10.37236/10866⟩. ⟨hal-04172966⟩
72 Consultations
64 Téléchargements

Altmetric

Partager

More