Unbalanced spanning subgraphs in edge labeled complete graphs
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\).
- scientific article; zbMATH DE number 861312
- Unbalanced signed graphs with extremal spectral radius or index
- Unbalanced unicyclic and bicyclic graphs with extremal spectral radius.
- scientific article; zbMATH DE number 4041966
- scientific article; zbMATH DE number 1874378
- On the uniformly balancedness of graphs
- On the edge-balanced index sets of complete bipartite graphs
- Unbalanced bipartite factorizations of complete bipartite graphs
- On uniformly balanced graphs
- A discrepancy version of the Hajnal-Szemerédi theorem
- A note on color-bias Hamilton cycles in dense graphs
- Alternating cycles and paths in edge-coloured multigraphs: A survey
- Efficiently finding low-sum copies of spanning forests in zero-sum complete graphs via conditional expectation
- Heavy paths and cycles in weighted graphs
- scientific article; zbMATH DE number 881162 (Why is no real title available?)
- Low weight perfect matchings
- On maximal paths and circuits of graphs
- On the discrepancies of graphs
- On the existence of zero-sum perfect matchings of complete graphs
- On zero-sum and almost zero-sum subgraphs over \(\mathbb Z\)
- On zero-sum spanning trees and zero-sum connectivity
- Unavoidable chromatic patterns in 2‐colorings of the complete graph
- Unavoidable patterns
- Unavoidable subgraphs of colored graphs
- Zero-sum copies of spanning forests in zero-sum complete graphs
- Zero-sum problems -- a survey
- Zero-sum problems in finite Abelian groups: a survey
This page was built for publication: Unbalanced spanning subgraphs in edge labeled complete graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2692172)
