On zero-sum spanning trees and zero-sum connectivity

DOI10.37236/10289MaRDI QIDQ2073300zbMATH OpenOpenAlexFDO

Authors Yair Caro, Adriana Hansberg, Josef Lauri, Christina Zarb

Publication date 1 February 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2007.08240

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(K_3\)-free graphscomplete graphsmaximal planar graphs\(d\)-treeszero-sum spanning pathzero-sum spanning tree

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Connectivity (05C40)

Abstract: We consider $2$-colourings $f:E(G)ightarrow-1,1$ of the edges of a graph $G$ with colours $-1$ and $1$ in $mathbbZ$. A subgraph $H$ of $G$ is said to be a zero-sum subgraph of $G$ under $f$ if $f(H):=su{m}_{einE(H)}f(e)=0$. We study the following type of questions, in several cases obtaining best possible results: Under which conditions on $|f(G)|$ can we guarantee the existence of a zero-sum spanning tree of $G$? The types of $G$ we consider are complete graphs, $K_3$-free graphs, $d$-trees, and maximal planar graphs. We also answer the question of when any such colouring contains a zero-sum spanning path or a zero-sum spanning tree of diameter at most $3$, showing in passing that the diameter-$3$ condition is best possible. Finally, we give, for $G=K_n$, a sharp bound on $|f(K_n)|$ by which an interesting zero-sum connectivity property is forced, namely that any two vertices are joined by a zero-sum path of length at most $4$. One feature of this paper is the proof of an Interpolation Lemma leading to a Master Theorem from which many of the above results follow and which can be of independent interest.

Recommendations

• Zero-sum copies of spanning forests in zero-sum complete graphs
• scientific article; zbMATH DE number 822737
• On three zero‐sum Ramsey‐type problems
• On zero-sum and almost zero-sum subgraphs over \(\mathbb Z\)
• scientific article; zbMATH DE number 85785

Cites work

• scientific article; zbMATH DE number 4137812 (Why is no real title available?)
• scientific article; zbMATH DE number 4103086 (Why is no real title available?)
• scientific article; zbMATH DE number 3503285 (Why is no real title available?)
• scientific article; zbMATH DE number 1286510 (Why is no real title available?)
• scientific article; zbMATH DE number 1452400 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3349817 (Why is no real title available?)
• k-Degenerate Graphs
• A complete characterization of the zero-sum (mod 2) Ramsey numbers
• A note on totally-omnitonal graphs
• A proof of Ringel's conjecture
• A simpler proof and a generalization of the zero-trees theorem
• Almost color-balanced perfect matchings in color-balanced complete graphs
• Diagonal forms of incidence matrices associated with \(t\)-uniform hypergraphs
• Every \(H\)-decomposition of \(K_n\) has a nearly resolvable alternative
• Large monochromatic components in edge colorings of graphs: A survey
• Low weight perfect matchings
• On simple characterizations of k-trees
• On the Turán number of forests
• On zero-sum and almost zero-sum subgraphs over \(\mathbb Z\)
• On zero-trees
• Packing graphs: The packing problem solved
• Resolution of the Oberwolfach problem
• Spanning subgraphs of a hypercube. IV: Rooted trees
• The Diameter of a Graph and its Complement
• The formula for Turán number of spanning linear forests
• The generalised Oberwolfach problem
• The uniformity space of hypergraphs and its applications
• Unavoidable chromatic patterns in 2‐colorings of the complete graph
• Zero-sum \(K_m\) over \(\mathbb{Z}\) and the story of \(K_4\)
• Zero-sum problems -- a survey
• Zero-sum subsequences in bounded-sum \(\{-1,1\}\)-sequences

Cited in

(12)

• Zero-sum copies of spanning forests in zero-sum complete graphs
• On the existence of zero-sum perfect matchings of complete graphs
• Efficiently finding low-sum copies of spanning forests in zero-sum complete graphs via conditional expectation
• On balanceable and simply balanceable regular graphs
• Almost color-balanced perfect matchings in color-balanced complete graphs
• On zero-sum and almost zero-sum subgraphs over \(\mathbb Z\)
• Balanced substructures in bicolored graphs
• On zero-trees
• The balancing number and generalized balancing number of some graph classes
• Unbalanced spanning subgraphs in edge labeled complete graphs
• Graphs isomorphisms under edge-replacements and the family of amoebas
• Zero-sum squares in \(\{-1, 1\}\)-matrices with low discrepancy

This page was built for publication: On zero-sum spanning trees and zero-sum connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2073300)