Integer flows on triangularly connected signed graphs Article Swipe

PDF

Liangchen Li , Chong Li , Rong Luo , Cun‐Quan Zhang ·

YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2310.13504

A triangle-path in a graph $G$ is a sequence of distinct triangles $T_1,T_2,\ldots,T_m$ in $G$ such that for any $i, j$ with $1\leq i < j \leq m$, $|E(T_i)\cap E(T_{i+1})|=1$ and $E(T_i)\cap E(T_j)=\emptyset$ if $j > i+1$. A connected graph $G$ is triangularly connected if for any two nonparallel edges $e$ and $e'$ there is a triangle-path $T_1T_2\cdots T_m$ such that $e\in E(T_1)$ and $e'\in E(T_m)$. For ordinary graphs, Fan {\it et al.}~(J. Combin. Theory Ser. B 98 (2008) 1325-1336) characterize all triangularly connected graphs that admit nowhere-zero $3$-flows or $4$-flows. Corollaries of this result include integer flow of some families of ordinary graphs, such as, locally connected graphs due to Lai (J. Graph Theory 42 (2003) 211-219) and some types of products of graphs due to Imrich et al.(J. Graph Theory 64 (2010) 267-276). In this paper, Fan's result for triangularly connected graphs is further extended to signed graphs. We proved that every flow-admissible triangularly connected signed graph admits a nowhere-zero $4$-flow if and only if it is not the wheel $W_5$ associated with a specific signature. Moreover, this result is sharp since there are infinitely many unbalanced triangularly connected signed graphs admitting a nowhere-zero $4$-flow but not $3$-flow.

Related Topics

Concepts

Combinatorics Mathematics Discrete mathematics Graph Path (computing) Integer (computer science) Zero (linguistics) Connectivity Computer science Philosophy Linguistics Programming language

Metadata

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

All OpenAlex metadata

Raw OpenAlex JSON

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

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

Digital Object Identifier
Title: Integer flows on triangularly connected signed graphs

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2023

Year of publication
Publication date: 2023-10-20

Full publication date if available
Authors: Liangchen Li, Chong Li, Rong Luo, Cun‐Quan Zhang

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

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

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/2310.13504

Direct OA link when available
Concepts: Combinatorics, Mathematics, Discrete mathematics, Graph, Path (computing), Integer (computer science), Zero (linguistics), Connectivity, Computer science, Philosophy, Linguistics, Programming language

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

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4387892113
doi	https://doi.org/10.48550/arxiv.2310.13504
ids.doi	https://doi.org/10.48550/arxiv.2310.13504
ids.openalex	https://openalex.org/W4387892113
fwci
type	preprint
title	Integer flows on triangularly connected signed graphs
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.9983999729156494
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.9962000250816345
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.9635000228881836
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/C114614502
concepts[0].level	1
concepts[0].score	0.7422013282775879
concepts[0].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[0].display_name	Combinatorics
concepts[1].id	https://openalex.org/C33923547
concepts[1].level	0
concepts[1].score	0.6706575751304626
concepts[1].wikidata	https://www.wikidata.org/wiki/Q395
concepts[1].display_name	Mathematics
concepts[2].id	https://openalex.org/C118615104
concepts[2].level	1
concepts[2].score	0.4979584217071533
concepts[2].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[2].display_name	Discrete mathematics
concepts[3].id	https://openalex.org/C132525143
concepts[3].level	2
concepts[3].score	0.47961485385894775
concepts[3].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[3].display_name	Graph
concepts[4].id	https://openalex.org/C2777735758
concepts[4].level	2
concepts[4].score	0.4487996995449066
concepts[4].wikidata	https://www.wikidata.org/wiki/Q817765
concepts[4].display_name	Path (computing)
concepts[5].id	https://openalex.org/C97137487
concepts[5].level	2
concepts[5].score	0.44584760069847107
concepts[5].wikidata	https://www.wikidata.org/wiki/Q729138
concepts[5].display_name	Integer (computer science)
concepts[6].id	https://openalex.org/C2780813799
concepts[6].level	2
concepts[6].score	0.44177037477493286
concepts[6].wikidata	https://www.wikidata.org/wiki/Q3274237
concepts[6].display_name	Zero (linguistics)
concepts[7].id	https://openalex.org/C76444178
concepts[7].level	3
concepts[7].score	0.41407883167266846
concepts[7].wikidata	https://www.wikidata.org/wiki/Q72897900
concepts[7].display_name	Connectivity
concepts[8].id	https://openalex.org/C41008148
concepts[8].level	0
concepts[8].score	0.11577239632606506
concepts[8].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[8].display_name	Computer science
concepts[9].id	https://openalex.org/C138885662
concepts[9].level	0
concepts[9].score	0.0
concepts[9].wikidata	https://www.wikidata.org/wiki/Q5891
concepts[9].display_name	Philosophy
concepts[10].id	https://openalex.org/C41895202
concepts[10].level	1
concepts[10].score	0.0
concepts[10].wikidata	https://www.wikidata.org/wiki/Q8162
concepts[10].display_name	Linguistics
concepts[11].id	https://openalex.org/C199360897
concepts[11].level	1
concepts[11].score	0.0
concepts[11].wikidata	https://www.wikidata.org/wiki/Q9143
concepts[11].display_name	Programming language
keywords[0].id	https://openalex.org/keywords/combinatorics
keywords[0].score	0.7422013282775879
keywords[0].display_name	Combinatorics
keywords[1].id	https://openalex.org/keywords/mathematics
keywords[1].score	0.6706575751304626
keywords[1].display_name	Mathematics
keywords[2].id	https://openalex.org/keywords/discrete-mathematics
keywords[2].score	0.4979584217071533
keywords[2].display_name	Discrete mathematics
keywords[3].id	https://openalex.org/keywords/graph
keywords[3].score	0.47961485385894775
keywords[3].display_name	Graph
keywords[4].id	https://openalex.org/keywords/path
keywords[4].score	0.4487996995449066
keywords[4].display_name	Path (computing)
keywords[5].id	https://openalex.org/keywords/integer
keywords[5].score	0.44584760069847107
keywords[5].display_name	Integer (computer science)
keywords[6].id	https://openalex.org/keywords/zero
keywords[6].score	0.44177037477493286
keywords[6].display_name	Zero (linguistics)
keywords[7].id	https://openalex.org/keywords/connectivity
keywords[7].score	0.41407883167266846
keywords[7].display_name	Connectivity
keywords[8].id	https://openalex.org/keywords/computer-science
keywords[8].score	0.11577239632606506
keywords[8].display_name	Computer science
language	en
locations[0].id	pmh:oai:arXiv.org:2310.13504
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/2310.13504
locations[0].version	submittedVersion
locations[0].raw_type
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/2310.13504
locations[1].id	doi:10.48550/arxiv.2310.13504
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	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
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.2310.13504
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5101647094
authorships[0].author.orcid	https://orcid.org/0000-0003-2234-0244
authorships[0].author.display_name	Liangchen Li
authorships[0].author_position	first
authorships[0].raw_author_name	Li, Liangchen
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5100412259
authorships[1].author.orcid	https://orcid.org/0009-0000-0708-7493
authorships[1].author.display_name	Chong Li
authorships[1].author_position	middle
authorships[1].raw_author_name	Li, Chong
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5066405314
authorships[2].author.orcid	https://orcid.org/0000-0002-5237-1001
authorships[2].author.display_name	Rong Luo
authorships[2].author_position	middle
authorships[2].raw_author_name	Luo, Rong
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5064703404
authorships[3].author.orcid	https://orcid.org/0000-0001-5583-4481
authorships[3].author.display_name	Cun‐Quan Zhang
authorships[3].author_position	last
authorships[3].raw_author_name	Zhang, Cun-Quan
authorships[3].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2310.13504
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Integer flows on triangularly connected signed graphs
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.9983999729156494
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/W3013650182, https://openalex.org/W2989283631, https://openalex.org/W4249605382, https://openalex.org/W4313491656, https://openalex.org/W3279617, https://openalex.org/W1991183963, https://openalex.org/W2053087750, https://openalex.org/W2384431448, https://openalex.org/W3189256254, https://openalex.org/W3161337494
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2310.13504
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/2310.13504
best_oa_location.version	submittedVersion
best_oa_location.raw_type
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/2310.13504
primary_location.id	pmh:oai:arXiv.org:2310.13504
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/2310.13504
primary_location.version	submittedVersion
primary_location.raw_type
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/2310.13504
publication_date	2023-10-20
publication_year	2023
referenced_works_count	0
abstract_inverted_index.A	0, 37
abstract_inverted_index.B	76
abstract_inverted_index.a	3, 7, 55, 160, 175, 194
abstract_inverted_index.i	23
abstract_inverted_index.j	25
abstract_inverted_index.$j	34
abstract_inverted_index.42	115
abstract_inverted_index.64	132
abstract_inverted_index.98	77
abstract_inverted_index.In	135
abstract_inverted_index.We	150
abstract_inverted_index.et	71, 128
abstract_inverted_index.if	33, 44, 163, 166
abstract_inverted_index.in	2, 13
abstract_inverted_index.is	6, 41, 54, 144, 168, 181
abstract_inverted_index.it	167
abstract_inverted_index.j$	20
abstract_inverted_index.of	9, 92, 98, 101, 121, 123
abstract_inverted_index.or	89
abstract_inverted_index.to	110, 126, 147
abstract_inverted_index.$G$	5, 14, 40
abstract_inverted_index.$e$	50
abstract_inverted_index.$i,	19
abstract_inverted_index.(J.	112
abstract_inverted_index.Fan	69
abstract_inverted_index.For	66
abstract_inverted_index.Lai	111
abstract_inverted_index.all	81
abstract_inverted_index.and	30, 51, 63, 118, 164
abstract_inverted_index.any	18, 46
abstract_inverted_index.are	185
abstract_inverted_index.as,	105
abstract_inverted_index.but	197
abstract_inverted_index.due	109, 125
abstract_inverted_index.for	17, 45, 140
abstract_inverted_index.m$,	27
abstract_inverted_index.not	169, 198
abstract_inverted_index.the	170
abstract_inverted_index.two	47
abstract_inverted_index.$e'$	52
abstract_inverted_index.>	35
abstract_inverted_index.<	24
abstract_inverted_index.Ser.	75
abstract_inverted_index.T_m$	58
abstract_inverted_index.\leq	26
abstract_inverted_index.flow	97
abstract_inverted_index.many	187
abstract_inverted_index.only	165
abstract_inverted_index.some	99, 119
abstract_inverted_index.such	15, 59, 104
abstract_inverted_index.that	16, 60, 85, 152
abstract_inverted_index.this	93, 136, 179
abstract_inverted_index.with	21, 174
abstract_inverted_index.{\it	70
abstract_inverted_index.$W_5$	172
abstract_inverted_index.$e\in	61
abstract_inverted_index.Fan's	138
abstract_inverted_index.Graph	113, 130
abstract_inverted_index.admit	86
abstract_inverted_index.edges	49
abstract_inverted_index.every	153
abstract_inverted_index.graph	4, 39, 158
abstract_inverted_index.i+1$.	36
abstract_inverted_index.sharp	182
abstract_inverted_index.since	183
abstract_inverted_index.there	53, 184
abstract_inverted_index.types	120
abstract_inverted_index.wheel	171
abstract_inverted_index.$1\leq	22
abstract_inverted_index.$e'\in	64
abstract_inverted_index.(2003)	116
abstract_inverted_index.(2008)	78
abstract_inverted_index.(2010)	133
abstract_inverted_index.Imrich	127
abstract_inverted_index.Theory	74, 114, 131
abstract_inverted_index.admits	159
abstract_inverted_index.al.(J.	129
abstract_inverted_index.graphs	84, 108, 124, 143, 192
abstract_inverted_index.paper,	137
abstract_inverted_index.proved	151
abstract_inverted_index.result	94, 139, 180
abstract_inverted_index.signed	148, 157, 191
abstract_inverted_index.Combin.	73
abstract_inverted_index.E(T_1)$	62
abstract_inverted_index.further	145
abstract_inverted_index.graphs,	68, 103
abstract_inverted_index.graphs.	149
abstract_inverted_index.include	95
abstract_inverted_index.integer	96
abstract_inverted_index.locally	106
abstract_inverted_index.$4$-flow	162, 196
abstract_inverted_index.211-219)	117
abstract_inverted_index.E(T_m)$.	65
abstract_inverted_index.al.}~(J.	72
abstract_inverted_index.distinct	10
abstract_inverted_index.extended	146
abstract_inverted_index.families	100
abstract_inverted_index.ordinary	67, 102
abstract_inverted_index.products	122
abstract_inverted_index.sequence	8
abstract_inverted_index.specific	176
abstract_inverted_index.$3$-flow.	199
abstract_inverted_index.$3$-flows	88
abstract_inverted_index.267-276).	134
abstract_inverted_index.Moreover,	178
abstract_inverted_index.admitting	193
abstract_inverted_index.connected	38, 43, 83, 107, 142, 156, 190
abstract_inverted_index.triangles	11
abstract_inverted_index.$4$-flows.	90
abstract_inverted_index.1325-1336)	79
abstract_inverted_index.associated	173
abstract_inverted_index.infinitely	186
abstract_inverted_index.signature.	177
abstract_inverted_index.unbalanced	188
abstract_inverted_index.$E(T_i)\cap	31
abstract_inverted_index.Corollaries	91
abstract_inverted_index.nonparallel	48
abstract_inverted_index.$\|E(T_i)\cap	28
abstract_inverted_index.characterize	80
abstract_inverted_index.nowhere-zero	87, 161, 195
abstract_inverted_index.triangularly	42, 82, 141, 155, 189
abstract_inverted_index.$T_1T_2\cdots	57
abstract_inverted_index.triangle-path	1, 56
abstract_inverted_index.E(T_{i+1})\|=1$	29
abstract_inverted_index.flow-admissible	154
abstract_inverted_index.E(T_j)=\emptyset$	32
abstract_inverted_index.$T_1,T_2,\ldots,T_m$	12
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile