Flows on signed graphs without long barbells Article Swipe

PDF

You Lu , Rong Luo , Michael Schubert , Eckhard Steffen , Cun‐Quan Zhang ·

YOU? · · 2019 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1908.11004

Many basic properties in Tutte's flow theory for unsigned graphs do not have their counterparts for signed graphs. However, signed graphs without long barbells in many ways behave like unsigned graphs from the point view of flows. In this paper, we study whether some basic properties in Tutte's flow theory remain valid for this family of signed graphs. Specifically let $(G,σ)$ be a flow-admissible signed graph without long barbells. We show that it admits a nowhere-zero $6$-flow and that it admits a nowhere-zero modulo $k$-flow if and only if it admits a nowhere-zero integer $k$-flow for each integer $k\geq 3$ and $k \not = 4$. We also show that each nowhere-zero positive integer $k$-flow of $(G,σ)$ can be expressed as the sum of some $2$-flows. For general graphs, we show that every nowhere-zero $\frac{p}{q}$-flow can be normalized in such a way, that each flow value is a multiple of $\frac{1}{2q}$. As a consequence we prove the equality of the integer flow number and the ceiling of the circular flow number for flow-admissible signed graphs without long barbells.

Related Topics

Concepts

Mathematics Combinatorics Signed graph Integer (computer science) Flow (mathematics) Modulo Zero (linguistics) Discrete mathematics Graph Geometry Computer science Philosophy Programming language Linguistics

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/1908.11004
PDF: https://arxiv.org/pdf/1908.11004
OA Status: green
References: 17
Related Works: 10
OpenAlex ID: https://openalex.org/W2971334413

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W2971334413

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.1908.11004

Digital Object Identifier
Title: Flows on signed graphs without long barbells

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2019

Year of publication
Publication date: 2019-08-29

Full publication date if available
Authors: You Lu, Rong Luo, Michael Schubert, Eckhard Steffen, Cun‐Quan Zhang

List of authors in order
Landing page: https://arxiv.org/abs/1908.11004

Publisher landing page
PDF URL: https://arxiv.org/pdf/1908.11004

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/1908.11004

Direct OA link when available
Concepts: Mathematics, Combinatorics, Signed graph, Integer (computer science), Flow (mathematics), Modulo, Zero (linguistics), Discrete mathematics, Graph, Geometry, Computer science, Philosophy, Programming language, Linguistics

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
References (count): 17

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W2971334413
doi	https://doi.org/10.48550/arxiv.1908.11004
ids.doi	https://doi.org/10.48550/arxiv.1908.11004
ids.mag	2971334413
ids.openalex	https://openalex.org/W2971334413
fwci
type	preprint
title	Flows on signed graphs without long barbells
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10374
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9998000264167786
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Advanced Graph Theory Research
topics[1].id	https://openalex.org/T11329
topics[1].field.id	https://openalex.org/fields/26
topics[1].field.display_name	Mathematics
topics[1].score	0.9987000226974487
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2607
topics[1].subfield.display_name	Discrete Mathematics and Combinatorics
topics[1].display_name	Limits and Structures in Graph Theory
topics[2].id	https://openalex.org/T10720
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9925000071525574
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1703
topics[2].subfield.display_name	Computational Theory and Mathematics
topics[2].display_name	Complexity and Algorithms in Graphs
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C33923547
concepts[0].level	0
concepts[0].score	0.7480150461196899
concepts[0].wikidata	https://www.wikidata.org/wiki/Q395
concepts[0].display_name	Mathematics
concepts[1].id	https://openalex.org/C114614502
concepts[1].level	1
concepts[1].score	0.7161462903022766
concepts[1].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[1].display_name	Combinatorics
concepts[2].id	https://openalex.org/C2779773260
concepts[2].level	3
concepts[2].score	0.6869921684265137
concepts[2].wikidata	https://www.wikidata.org/wiki/Q11246292
concepts[2].display_name	Signed graph
concepts[3].id	https://openalex.org/C97137487
concepts[3].level	2
concepts[3].score	0.6050374507904053
concepts[3].wikidata	https://www.wikidata.org/wiki/Q729138
concepts[3].display_name	Integer (computer science)
concepts[4].id	https://openalex.org/C38349280
concepts[4].level	2
concepts[4].score	0.5691563487052917
concepts[4].wikidata	https://www.wikidata.org/wiki/Q1434290
concepts[4].display_name	Flow (mathematics)
concepts[5].id	https://openalex.org/C54732982
concepts[5].level	2
concepts[5].score	0.5591388940811157
concepts[5].wikidata	https://www.wikidata.org/wiki/Q1415345
concepts[5].display_name	Modulo
concepts[6].id	https://openalex.org/C2780813799
concepts[6].level	2
concepts[6].score	0.5152013897895813
concepts[6].wikidata	https://www.wikidata.org/wiki/Q3274237
concepts[6].display_name	Zero (linguistics)
concepts[7].id	https://openalex.org/C118615104
concepts[7].level	1
concepts[7].score	0.4885209798812866
concepts[7].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[7].display_name	Discrete mathematics
concepts[8].id	https://openalex.org/C132525143
concepts[8].level	2
concepts[8].score	0.3947239816188812
concepts[8].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[8].display_name	Graph
concepts[9].id	https://openalex.org/C2524010
concepts[9].level	1
concepts[9].score	0.11197876930236816
concepts[9].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[9].display_name	Geometry
concepts[10].id	https://openalex.org/C41008148
concepts[10].level	0
concepts[10].score	0.08733657002449036
concepts[10].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[10].display_name	Computer science
concepts[11].id	https://openalex.org/C138885662
concepts[11].level	0
concepts[11].score	0.0
concepts[11].wikidata	https://www.wikidata.org/wiki/Q5891
concepts[11].display_name	Philosophy
concepts[12].id	https://openalex.org/C199360897
concepts[12].level	1
concepts[12].score	0.0
concepts[12].wikidata	https://www.wikidata.org/wiki/Q9143
concepts[12].display_name	Programming language
concepts[13].id	https://openalex.org/C41895202
concepts[13].level	1
concepts[13].score	0.0
concepts[13].wikidata	https://www.wikidata.org/wiki/Q8162
concepts[13].display_name	Linguistics
keywords[0].id	https://openalex.org/keywords/mathematics
keywords[0].score	0.7480150461196899
keywords[0].display_name	Mathematics
keywords[1].id	https://openalex.org/keywords/combinatorics
keywords[1].score	0.7161462903022766
keywords[1].display_name	Combinatorics
keywords[2].id	https://openalex.org/keywords/signed-graph
keywords[2].score	0.6869921684265137
keywords[2].display_name	Signed graph
keywords[3].id	https://openalex.org/keywords/integer
keywords[3].score	0.6050374507904053
keywords[3].display_name	Integer (computer science)
keywords[4].id	https://openalex.org/keywords/flow
keywords[4].score	0.5691563487052917
keywords[4].display_name	Flow (mathematics)
keywords[5].id	https://openalex.org/keywords/modulo
keywords[5].score	0.5591388940811157
keywords[5].display_name	Modulo
keywords[6].id	https://openalex.org/keywords/zero
keywords[6].score	0.5152013897895813
keywords[6].display_name	Zero (linguistics)
keywords[7].id	https://openalex.org/keywords/discrete-mathematics
keywords[7].score	0.4885209798812866
keywords[7].display_name	Discrete mathematics
keywords[8].id	https://openalex.org/keywords/graph
keywords[8].score	0.3947239816188812
keywords[8].display_name	Graph
keywords[9].id	https://openalex.org/keywords/geometry
keywords[9].score	0.11197876930236816
keywords[9].display_name	Geometry
keywords[10].id	https://openalex.org/keywords/computer-science
keywords[10].score	0.08733657002449036
keywords[10].display_name	Computer science
language	en
locations[0].id	pmh:oai:arXiv.org:1908.11004
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/1908.11004
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/1908.11004
locations[1].id	doi:10.48550/arxiv.1908.11004
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.1908.11004
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5004663151
authorships[0].author.orcid	https://orcid.org/0000-0002-7693-9175
authorships[0].author.display_name	You Lu
authorships[0].countries	CN
authorships[0].affiliations[0].institution_ids	https://openalex.org/I17145004
authorships[0].affiliations[0].raw_affiliation_string	Northwestern Polytechnical University
authorships[0].institutions[0].id	https://openalex.org/I17145004
authorships[0].institutions[0].ror	https://ror.org/01y0j0j86
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I17145004
authorships[0].institutions[0].country_code	CN
authorships[0].institutions[0].display_name	Northwestern Polytechnical University
authorships[0].author_position	first
authorships[0].raw_author_name	You Lu
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	Northwestern Polytechnical University
authorships[1].author.id	https://openalex.org/A5066405314
authorships[1].author.orcid	https://orcid.org/0000-0002-5237-1001
authorships[1].author.display_name	Rong Luo
authorships[1].countries	US
authorships[1].affiliations[0].institution_ids	https://openalex.org/I12097938
authorships[1].affiliations[0].raw_affiliation_string	WEST VIRGINIA UNIVERSITY
authorships[1].institutions[0].id	https://openalex.org/I12097938
authorships[1].institutions[0].ror	https://ror.org/011vxgd24
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I12097938
authorships[1].institutions[0].country_code	US
authorships[1].institutions[0].display_name	West Virginia University
authorships[1].author_position	middle
authorships[1].raw_author_name	Rong Luo
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	WEST VIRGINIA UNIVERSITY
authorships[2].author.id	https://openalex.org/A5020865318
authorships[2].author.orcid	https://orcid.org/0000-0002-2341-712X
authorships[2].author.display_name	Michael Schubert
authorships[2].countries	DE
authorships[2].affiliations[0].institution_ids	https://openalex.org/I206945453
authorships[2].affiliations[0].raw_affiliation_string	Paderborn Univ.
authorships[2].institutions[0].id	https://openalex.org/I206945453
authorships[2].institutions[0].ror	https://ror.org/058kzsd48
authorships[2].institutions[0].type	education
authorships[2].institutions[0].lineage	https://openalex.org/I206945453
authorships[2].institutions[0].country_code	DE
authorships[2].institutions[0].display_name	Paderborn University
authorships[2].author_position	middle
authorships[2].raw_author_name	Michael Schubert
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	Paderborn Univ.
authorships[3].author.id	https://openalex.org/A5041562341
authorships[3].author.orcid	https://orcid.org/0000-0002-9808-7401
authorships[3].author.display_name	Eckhard Steffen
authorships[3].countries	DE
authorships[3].affiliations[0].institution_ids	https://openalex.org/I206945453
authorships[3].affiliations[0].raw_affiliation_string	Paderborn Univ.
authorships[3].institutions[0].id	https://openalex.org/I206945453
authorships[3].institutions[0].ror	https://ror.org/058kzsd48
authorships[3].institutions[0].type	education
authorships[3].institutions[0].lineage	https://openalex.org/I206945453
authorships[3].institutions[0].country_code	DE
authorships[3].institutions[0].display_name	Paderborn University
authorships[3].author_position	middle
authorships[3].raw_author_name	Eckhard Steffen
authorships[3].is_corresponding	False
authorships[3].raw_affiliation_strings	Paderborn Univ.
authorships[4].author.id	https://openalex.org/A5064703404
authorships[4].author.orcid	https://orcid.org/0000-0001-5583-4481
authorships[4].author.display_name	Cun‐Quan Zhang
authorships[4].countries	US
authorships[4].affiliations[0].institution_ids	https://openalex.org/I12097938
authorships[4].affiliations[0].raw_affiliation_string	WEST VIRGINIA UNIVERSITY
authorships[4].institutions[0].id	https://openalex.org/I12097938
authorships[4].institutions[0].ror	https://ror.org/011vxgd24
authorships[4].institutions[0].type	education
authorships[4].institutions[0].lineage	https://openalex.org/I12097938
authorships[4].institutions[0].country_code	US
authorships[4].institutions[0].display_name	West Virginia University
authorships[4].author_position	last
authorships[4].raw_author_name	Cun-Quan Zhang
authorships[4].is_corresponding	False
authorships[4].raw_affiliation_strings	WEST VIRGINIA UNIVERSITY
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/1908.11004
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Flows on signed graphs without long barbells
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10374
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9998000264167786
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Advanced Graph Theory Research
related_works	https://openalex.org/W2117548279, https://openalex.org/W2097470475, https://openalex.org/W2070252991, https://openalex.org/W2807449856, https://openalex.org/W2941201715, https://openalex.org/W2025727968, https://openalex.org/W238211858, https://openalex.org/W2803761277, https://openalex.org/W4297742300, https://openalex.org/W2195798288
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:1908.11004
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/1908.11004
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/1908.11004
primary_location.id	pmh:oai:arXiv.org:1908.11004
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/1908.11004
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/1908.11004
publication_date	2019-08-29
publication_year	2019
referenced_works	https://openalex.org/W2963579267, https://openalex.org/W2088648195, https://openalex.org/W2075480893, https://openalex.org/W2008049764, https://openalex.org/W1768269978, https://openalex.org/W1976047413, https://openalex.org/W1973282300, https://openalex.org/W2068987903, https://openalex.org/W2513228781, https://openalex.org/W1964553741, https://openalex.org/W2087420573, https://openalex.org/W2090562334, https://openalex.org/W2032431189, https://openalex.org/W1985061810, https://openalex.org/W2085123825, https://openalex.org/W2342659808, https://openalex.org/W2314361409
referenced_works_count	17
abstract_inverted_index.=	103
abstract_inverted_index.a	62, 74, 81, 91, 139, 146, 151
abstract_inverted_index.$k	101
abstract_inverted_index.3$	99
abstract_inverted_index.As	150
abstract_inverted_index.In	37
abstract_inverted_index.We	69, 105
abstract_inverted_index.as	119
abstract_inverted_index.be	61, 117, 135
abstract_inverted_index.do	10
abstract_inverted_index.if	85, 88
abstract_inverted_index.in	3, 24, 46, 137
abstract_inverted_index.is	145
abstract_inverted_index.it	72, 79, 89
abstract_inverted_index.of	35, 55, 114, 122, 148, 157, 165
abstract_inverted_index.we	40, 128, 153
abstract_inverted_index.4$.	104
abstract_inverted_index.For	125
abstract_inverted_index.and	77, 86, 100, 162
abstract_inverted_index.can	116, 134
abstract_inverted_index.for	7, 15, 52, 95, 170
abstract_inverted_index.let	59
abstract_inverted_index.not	11
abstract_inverted_index.sum	121
abstract_inverted_index.the	32, 120, 155, 158, 163, 166
abstract_inverted_index.Many	0
abstract_inverted_index.\not	102
abstract_inverted_index.also	106
abstract_inverted_index.each	96, 109, 142
abstract_inverted_index.flow	5, 48, 143, 160, 168
abstract_inverted_index.from	31
abstract_inverted_index.have	12
abstract_inverted_index.like	28
abstract_inverted_index.long	22, 67, 175
abstract_inverted_index.many	25
abstract_inverted_index.only	87
abstract_inverted_index.show	70, 107, 129
abstract_inverted_index.some	43, 123
abstract_inverted_index.such	138
abstract_inverted_index.that	71, 78, 108, 130, 141
abstract_inverted_index.this	38, 53
abstract_inverted_index.view	34
abstract_inverted_index.way,	140
abstract_inverted_index.ways	26
abstract_inverted_index.basic	1, 44
abstract_inverted_index.every	131
abstract_inverted_index.graph	65
abstract_inverted_index.point	33
abstract_inverted_index.prove	154
abstract_inverted_index.study	41
abstract_inverted_index.their	13
abstract_inverted_index.valid	51
abstract_inverted_index.value	144
abstract_inverted_index.$k\geq	98
abstract_inverted_index.admits	73, 80, 90
abstract_inverted_index.behave	27
abstract_inverted_index.family	54
abstract_inverted_index.flows.	36
abstract_inverted_index.graphs	9, 20, 30, 173
abstract_inverted_index.modulo	83
abstract_inverted_index.number	161, 169
abstract_inverted_index.paper,	39
abstract_inverted_index.remain	50
abstract_inverted_index.signed	16, 19, 56, 64, 172
abstract_inverted_index.theory	6, 49
abstract_inverted_index.Tutte's	4, 47
abstract_inverted_index.ceiling	164
abstract_inverted_index.general	126
abstract_inverted_index.graphs,	127
abstract_inverted_index.graphs.	17, 57
abstract_inverted_index.integer	93, 97, 112, 159
abstract_inverted_index.whether	42
abstract_inverted_index.without	21, 66, 174
abstract_inverted_index.$(G,σ)$	60, 115
abstract_inverted_index.$6$-flow	76
abstract_inverted_index.$k$-flow	84, 94, 113
abstract_inverted_index.However,	18
abstract_inverted_index.barbells	23
abstract_inverted_index.circular	167
abstract_inverted_index.equality	156
abstract_inverted_index.multiple	147
abstract_inverted_index.positive	111
abstract_inverted_index.unsigned	8, 29
abstract_inverted_index.barbells.	68, 176
abstract_inverted_index.expressed	118
abstract_inverted_index.$2$-flows.	124
abstract_inverted_index.normalized	136
abstract_inverted_index.properties	2, 45
abstract_inverted_index.consequence	152
abstract_inverted_index.Specifically	58
abstract_inverted_index.counterparts	14
abstract_inverted_index.nowhere-zero	75, 82, 92, 110, 132
abstract_inverted_index.$\frac{1}{2q}$.	149
abstract_inverted_index.flow-admissible	63, 171
abstract_inverted_index.$\frac{p}{q}$-flow	133
cited_by_percentile_year
countries_distinct_count	3
institutions_distinct_count	5
citation_normalized_percentile