Shortest circuit covers of signed graphs Article Swipe

PDF

Jian Cheng , You Lu , Rong Luo , Cun‐Quan Zhang ·

YOU? · · 2015 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1510.05717

A shortest circuit cover ${\cal F}$ of a bridgeless graph $G$ is a family of circuits that covers every edge of $G$ and is of minimum total length. The total length of a shortest circuit cover ${\cal F}$ of $G$ is denoted by $SCC(G)$. For ordinary graphs (graphs without sign), the subject of shortest circuit cover is closely related to some mainstream areas, such as, Tutte's integer flow theory, circuit double cover conjecture, Fulkerson conjecture, and others. For signed graphs $G$, it is proved recently by Máčajová, Raspaud, Rollová and Škoviera that $SCC(G) \leq 11|E|$ if $G$ is s-bridgeless, and $SCC(G) \leq 9|E|$ if $G$ is $2$-edge-connected. In this paper this result is improved as follows, $$SCC(G) ~ \leq ~ |E| + 3|V| +z$$ where $z ~=~ \min \{ \frac{2}{3}|E|+\frac{4}{3}ε_N-7,~ |V| + 2ε_N -8\}$ and $ε_N$ is the negativeness of $G$. The above upper bound can be further reduced if $G$ is $2$-edge-connected with even negativeness.

Related Topics

Combinatorics

Mathematics

Discrete Mathematics

Mathematical Analysis

Engineering

Mechanical Engineering

Concepts

Combinatorics Mathematics Conjecture Cover (algebra) Discrete mathematics Graph Upper and lower bounds Mathematical analysis Engineering Mechanical engineering

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/1510.05717
PDF: https://arxiv.org/pdf/1510.05717
OA Status: green
Cited By: 4
References: 9
Related Works: 10
OpenAlex ID: https://openalex.org/W1768443100

All OpenAlex metadata

Raw OpenAlex JSON

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

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

Digital Object Identifier
Title: Shortest circuit covers of signed graphs

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2015

Year of publication
Publication date: 2015-10-19

Full publication date if available
Authors: Jian Cheng, You Lu, Rong Luo, Cun‐Quan Zhang

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

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

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

Direct OA link when available
Concepts: Combinatorics, Mathematics, Conjecture, Cover (algebra), Discrete mathematics, Graph, Upper and lower bounds, Mathematical analysis, Engineering, Mechanical engineering

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

Total citation count in OpenAlex
Citations by year (recent): 2018: 2, 2017: 1, 2016: 1

Per-year citation counts (last 5 years)
References (count): 9

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

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W1768443100
doi	https://doi.org/10.48550/arxiv.1510.05717
ids.doi	https://doi.org/10.48550/arxiv.1510.05717
ids.mag	1768443100
ids.openalex	https://openalex.org/W1768443100
fwci
type	preprint
title	Shortest circuit covers of 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.9976999759674072
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/T10829
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9896000027656555
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1705
topics[1].subfield.display_name	Computer Networks and Communications
topics[1].display_name	Interconnection Networks and Systems
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.9851999878883362
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.8058158159255981
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.7047775983810425
concepts[1].wikidata	https://www.wikidata.org/wiki/Q395
concepts[1].display_name	Mathematics
concepts[2].id	https://openalex.org/C2780990831
concepts[2].level	2
concepts[2].score	0.643290102481842
concepts[2].wikidata	https://www.wikidata.org/wiki/Q319141
concepts[2].display_name	Conjecture
concepts[3].id	https://openalex.org/C2780428219
concepts[3].level	2
concepts[3].score	0.6102997064590454
concepts[3].wikidata	https://www.wikidata.org/wiki/Q16952335
concepts[3].display_name	Cover (algebra)
concepts[4].id	https://openalex.org/C118615104
concepts[4].level	1
concepts[4].score	0.47613218426704407
concepts[4].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[4].display_name	Discrete mathematics
concepts[5].id	https://openalex.org/C132525143
concepts[5].level	2
concepts[5].score	0.43433618545532227
concepts[5].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[5].display_name	Graph
concepts[6].id	https://openalex.org/C77553402
concepts[6].level	2
concepts[6].score	0.42229244112968445
concepts[6].wikidata	https://www.wikidata.org/wiki/Q13222579
concepts[6].display_name	Upper and lower bounds
concepts[7].id	https://openalex.org/C134306372
concepts[7].level	1
concepts[7].score	0.10483169555664062
concepts[7].wikidata	https://www.wikidata.org/wiki/Q7754
concepts[7].display_name	Mathematical analysis
concepts[8].id	https://openalex.org/C127413603
concepts[8].level	0
concepts[8].score	0.0
concepts[8].wikidata	https://www.wikidata.org/wiki/Q11023
concepts[8].display_name	Engineering
concepts[9].id	https://openalex.org/C78519656
concepts[9].level	1
concepts[9].score	0.0
concepts[9].wikidata	https://www.wikidata.org/wiki/Q101333
concepts[9].display_name	Mechanical engineering
keywords[0].id	https://openalex.org/keywords/combinatorics
keywords[0].score	0.8058158159255981
keywords[0].display_name	Combinatorics
keywords[1].id	https://openalex.org/keywords/mathematics
keywords[1].score	0.7047775983810425
keywords[1].display_name	Mathematics
keywords[2].id	https://openalex.org/keywords/conjecture
keywords[2].score	0.643290102481842
keywords[2].display_name	Conjecture
keywords[3].id	https://openalex.org/keywords/cover
keywords[3].score	0.6102997064590454
keywords[3].display_name	Cover (algebra)
keywords[4].id	https://openalex.org/keywords/discrete-mathematics
keywords[4].score	0.47613218426704407
keywords[4].display_name	Discrete mathematics
keywords[5].id	https://openalex.org/keywords/graph
keywords[5].score	0.43433618545532227
keywords[5].display_name	Graph
keywords[6].id	https://openalex.org/keywords/upper-and-lower-bounds
keywords[6].score	0.42229244112968445
keywords[6].display_name	Upper and lower bounds
keywords[7].id	https://openalex.org/keywords/mathematical-analysis
keywords[7].score	0.10483169555664062
keywords[7].display_name	Mathematical analysis
language	en
locations[0].id	pmh:oai:arXiv.org:1510.05717
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/1510.05717
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/1510.05717
locations[1].id	doi:10.48550/arxiv.1510.05717
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.1510.05717
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5113834335
authorships[0].author.orcid
authorships[0].author.display_name	Jian Cheng
authorships[0].author_position	first
authorships[0].raw_author_name	Jian Cheng
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5004663151
authorships[1].author.orcid	https://orcid.org/0000-0002-7693-9175
authorships[1].author.display_name	You Lu
authorships[1].author_position	middle
authorships[1].raw_author_name	You Lu
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	Rong Luo
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	Cun-Quan Zhang
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/1510.05717
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Shortest circuit covers of 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.9976999759674072
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/W4391375266, https://openalex.org/W4232403550, https://openalex.org/W623607250, https://openalex.org/W4245429118, https://openalex.org/W4205110281, https://openalex.org/W4212927854, https://openalex.org/W4211151614, https://openalex.org/W4244798043, https://openalex.org/W4361866086, https://openalex.org/W4251969024
cited_by_count	4
counts_by_year[0].year	2018
counts_by_year[0].cited_by_count	2
counts_by_year[1].year	2017
counts_by_year[1].cited_by_count	1
counts_by_year[2].year	2016
counts_by_year[2].cited_by_count	1
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:1510.05717
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/1510.05717
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/1510.05717
primary_location.id	pmh:oai:arXiv.org:1510.05717
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/1510.05717
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/1510.05717
publication_date	2015-10-19
publication_year	2015
referenced_works	https://openalex.org/W1991592444, https://openalex.org/W1543349373, https://openalex.org/W2051565157, https://openalex.org/W2021628833, https://openalex.org/W2093198214, https://openalex.org/W2068987903, https://openalex.org/W1968574902, https://openalex.org/W2013356944, https://openalex.org/W1977200224
referenced_works_count	9
abstract_inverted_index.+	121, 131
abstract_inverted_index.A	0
abstract_inverted_index.a	7, 12, 32
abstract_inverted_index.~	117, 119
abstract_inverted_index.$z	125
abstract_inverted_index.In	107
abstract_inverted_index.\{	128
abstract_inverted_index.as	114
abstract_inverted_index.be	146
abstract_inverted_index.by	42, 85
abstract_inverted_index.if	95, 103, 149
abstract_inverted_index.is	11, 23, 40, 56, 82, 97, 105, 112, 136, 151
abstract_inverted_index.it	81
abstract_inverted_index.of	6, 14, 20, 24, 31, 38, 52, 139
abstract_inverted_index.to	59
abstract_inverted_index.$G$	10, 21, 39, 96, 104, 150
abstract_inverted_index.For	44, 77
abstract_inverted_index.F}$	5, 37
abstract_inverted_index.The	28, 141
abstract_inverted_index.and	22, 75, 89, 99, 134
abstract_inverted_index.as,	64
abstract_inverted_index.can	145
abstract_inverted_index.the	50, 137
abstract_inverted_index.\|E\|	120
abstract_inverted_index.\|V\|	130
abstract_inverted_index.~=~	126
abstract_inverted_index.$G$,	80
abstract_inverted_index.$G$.	140
abstract_inverted_index.+z$$	123
abstract_inverted_index.3\|V\|	122
abstract_inverted_index.\leq	93, 101, 118
abstract_inverted_index.\min	127
abstract_inverted_index.edge	19
abstract_inverted_index.even	154
abstract_inverted_index.flow	67
abstract_inverted_index.some	60
abstract_inverted_index.such	63
abstract_inverted_index.that	16, 91
abstract_inverted_index.this	108, 110
abstract_inverted_index.with	153
abstract_inverted_index.-8\}$	133
abstract_inverted_index.2ε_N	132
abstract_inverted_index.9\|E\|$	102
abstract_inverted_index.above	142
abstract_inverted_index.bound	144
abstract_inverted_index.cover	3, 35, 55, 71
abstract_inverted_index.every	18
abstract_inverted_index.graph	9
abstract_inverted_index.paper	109
abstract_inverted_index.total	26, 29
abstract_inverted_index.upper	143
abstract_inverted_index.where	124
abstract_inverted_index.${\cal	4, 36
abstract_inverted_index.$ε_N$	135
abstract_inverted_index.11\|E\|$	94
abstract_inverted_index.areas,	62
abstract_inverted_index.covers	17
abstract_inverted_index.double	70
abstract_inverted_index.family	13
abstract_inverted_index.graphs	46, 79
abstract_inverted_index.length	30
abstract_inverted_index.proved	83
abstract_inverted_index.result	111
abstract_inverted_index.sign),	49
abstract_inverted_index.signed	78
abstract_inverted_index.$SCC(G)	92, 100
abstract_inverted_index.(graphs	47
abstract_inverted_index.Tutte's	65
abstract_inverted_index.circuit	2, 34, 54, 69
abstract_inverted_index.closely	57
abstract_inverted_index.denoted	41
abstract_inverted_index.further	147
abstract_inverted_index.integer	66
abstract_inverted_index.length.	27
abstract_inverted_index.minimum	25
abstract_inverted_index.others.	76
abstract_inverted_index.reduced	148
abstract_inverted_index.related	58
abstract_inverted_index.subject	51
abstract_inverted_index.theory,	68
abstract_inverted_index.without	48
abstract_inverted_index.$$SCC(G)	116
abstract_inverted_index.Raspaud,	87
abstract_inverted_index.Rollová	88
abstract_inverted_index.circuits	15
abstract_inverted_index.follows,	115
abstract_inverted_index.improved	113
abstract_inverted_index.ordinary	45
abstract_inverted_index.recently	84
abstract_inverted_index.shortest	1, 33, 53
abstract_inverted_index.$SCC(G)$.	43
abstract_inverted_index.Fulkerson	73
abstract_inverted_index.Škoviera	90
abstract_inverted_index.bridgeless	8
abstract_inverted_index.mainstream	61
abstract_inverted_index.conjecture,	72, 74
abstract_inverted_index.Máčajová,	86
abstract_inverted_index.negativeness	138
abstract_inverted_index.negativeness.	155
abstract_inverted_index.s-bridgeless,	98
abstract_inverted_index.$2$-edge-connected	152
abstract_inverted_index.$2$-edge-connected.	106
abstract_inverted_index.\frac{2}{3}\|E\|+\frac{4}{3}ε_N-7,~	129
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile