Unbalanced spanning subgraphs in edge labeled complete graphs
type: Item
instance of: scholarly article
title: Unbalanced spanning subgraphs in edge labeled complete graphs
DOI: 10.37236/10866
author: Johannes Pardey
author: L. Picasarri-Arrieta
author: Dieter Rautenbach
author: Stéphane Bessy
published in: The Electronic Journal of Combinatorics
publication date: 2023-03-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/2107.09290
review text: For a complete graph on \(n\) vertices, an edge labeling is said to be balanced if there are equally many plus-edges and minus-edges, that is edges with label \(+1\) and \(-1\), respectively. The authors are stimulated by the work of \textit{Y. Caro} et al. [``Unavoidable chromatic patterns in 2-colorings of the complete graph'', J. Graph Theory 97, 123--147 (2021; \url{doi.org/10.1002/jgt.22645})] on omnitonal graphs. A graph \(G\) is said to be omnitonal if for every pair \((K,c)\), where the order \(n\) of \(K\) is sufficiently large and there are sufficiently many plus-edges and minus-edges in \(K\), and for every two non-negative integers \(m^+\) and \(m^-\) with \(m(G)=m^++m^-\), there is an isomorphic copy \(G'\) of \(G\) in \(K\) with \(m^+(G^\prime)=m^+\) and \(m-(G^\prime)=m^-\). What is new in this study is that the order of \(K\) is necessarily much bigger than the order of \(G\), that is, the graph \(G\) is far from being a spanning subgraph of \(K\). Noting the fact that the higher the density of a spanning graph \(G\) is, the more every isomorphic copy of \(G\) in \(K\) is forced to reproduce the density of plus- and minus-edges in \((K,c)\) the authors consider graphs of bounded maximum degree as a natural hypothesis excluding dense spanning subgraphs. The authors prove the existence of an isomorphic copy \(G^\prime\) of \(G\) in \(K\) such that the number of edges with label \(+1\) in \(G^\prime\) exceeds the expected value \(d\) times \(m(G)\) when considering a uniformly random copy of \(G\) in \(K\).
reviewed by: V. Yegnanarayanan
Mathematics Subject Classification ID: 05C22
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C76
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 7666312
zbMATH Keywords: local irregularity
zbMATH Keywords: corona product
zbMATH Keywords: tree graph family
MaRDI profile type: Publication
OpenAlex ID: W3183237568
cites work: Alternating cycles and paths in edge-coloured multigraphs: A survey
cites work: On the discrepancies of graphs
cites work: A discrepancy version of the Hajnal–Szemerédi theorem
cites work: Zero-sum problems -- a survey
cites work: On zero-sum spanning trees and zero-sum connectivity
cites work: Unavoidable chromatic patterns in 2‐colorings of the complete graph
cites work: On zero-sum and almost zero-sum subgraphs over \(\mathbb Z\)
cites work: Unavoidable subgraphs of colored graphs
cites work: Low weight perfect matchings
cites work: On maximal paths and circuits of graphs
cites work: Q4878286
cites work: A Note on Color-Bias Hamilton Cycles in Dense Graphs
cites work: Unavoidable patterns
cites work: Zero-sum problems in finite Abelian groups: a survey
cites work: On the existence of zero-sum perfect matchings of complete graphs
cites work: Zero-sum copies of spanning forests in zero-sum complete graphs
cites work: Efficiently finding low-sum copies of spanning forests in zero-sum complete graphs via conditional expectation
cites work: Heavy paths and cycles in weighted graphs
Recommended article: Q4871036
Recommended article: Unbalanced signed graphs with extremal spectral radius or index
Recommended article: Unbalanced unicyclic and bicyclic graphs with extremal spectral radius
Recommended article: Q3781137
Recommended article: Q4795850
Recommended article: Q3170255
Recommended article: On the Edge-balanced Index Sets of Complete Bipartite Graphs
Recommended article: Unbalanced bipartite factorizations of complete bipartite graphs
Recommended article: On uniformly balanced graphs
description: scientific article; zbMATH DE number 7666312