On 1-sum flows in undirected graphs

DOI10.13001/1081-3810.3003MaRDI QIDQ2834760zbMATH OpenOpenAlexFDO

Authors S. Akbari, Klas Markström, S. Zare, S. Friedland

Publication date 24 November 2016

Published in ELA. The Electronic Journal of Linear Algebra (Search for Journal in Brave)

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

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

bipartite graph\(\gamma\)-\(L\)-flow\(c\)-sum flow\(L\)-flow

Mathematics Subject Classification ID

Linear programming (90C05) Flows in graphs (05C21)

Abstract: Let G=(V,E) be a simple undirected graph. For a given set L of the real line, a function omega from E to L is called an L-flow. Given a vector gamma whose coordinates are indexed by V, we say that omega is a gamma-L-flow if for each v in V, the sum of the values on the edges incident to v is gamma(v). If gamma(v)=c, for all v in V, then the gamma-L-flow is called a c-sum L-flow. In this paper we study the existence of gamma-L-flows for various choices of sets L of real numbers, with an emphasis on 1-sum flows. Given a natural k number, a c-sum k-flow is a c-sum flow with values from the set {-1,1,...,1-k, k-1}. Let L be a subset of real numbers containing 0 and let L* be L minus 0 by L*. Answering a question from a recent paper we characterize which bipartite graphs admit a 1-sum R*-flow or a 1-sum Z*-flow. We also show that that every k-regular graph, with k either odd or congruent to 2 modulo 4, admits a 1-sum {-1, 0, 1}-flow.

Recommendations

• 0-sum and 1-sum flows in regular graphs
• A generalization of 0-sum flows in graphs
• Zero-sum flows in regular graphs
• Constant sum flows in regular graphs
• Zero-sum flow numbers of regular graphs

Cites work

• scientific article; zbMATH DE number 3078983 (Why is no real title available?)
• scientific article; zbMATH DE number 3095897 (Why is no real title available?)
• A Contribution to the Theory of Chromatic Polynomials
• A generalization of 0-sum flows in graphs
• A note on zero-sum 5-flows in regular graphs
• An introduction to the theory of graph spectra
• Edge-Disjoint Spanning Trees of Finite Graphs
• Factors and factorizations of graphs. Proof techniques in factor theory
• Factors of regular graphs
• Flows and generalized coloring theorems in graphs
• Nowhere-zero 6-flows
• On factors in random graphs
• On the Problem of Decomposing a Graph into n Connected Factors
• On the extreme points of a certain convex polytope
• On zero-sum 6-flows of graphs
• Spanning trees with pairwise nonadjacent endvertices
• The 1-Factors of Oriented Graphs
• The Factorization of Linear Graphs
• Zero-sum flows in regular graphs

Cited in

(1)

• A generalization of 0-sum flows in graphs

This page was built for publication: On 1-sum flows in undirected graphs

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