Portal de Periódicos da CAPES

Circuit Covers of Signed Graphs

2015; Wiley; Volume: 81; Issue: 2 Linguagem: Inglês

10.1002/jgt.21866

1097-0118

Edita Máčajová, André Raspaud, Edita Rollová, Martin Škoviera,

Computational Geometry and Mesh Generation

Journal of Graph TheoryVolume 81, Issue 2 p. 120-133 Article Circuit Covers of Signed Graphs Edita Máčajová, Edita Máčajová [email protected] DEPARTMENT OF COMPUTER SCIENCE, COMENIUS UNIVERSITY, MLYNSKÁ DOLINA, 842 48 BRATISLAVA, SLOVAKIASearch for more papers by this authorAndré Raspaud, André Raspaud [email protected] LABRI, UNIVERSITE DE BORDEAUX, 33405 TALENCE CEDEX, FRANCESearch for more papers by this authorEdita Rollová, Edita Rollová [email protected] NTIS - NEW TECHNOLOGIES FOR THE INFORMATION SOCIETY, UNIVERSITY OF WEST BOHEMIA, UNIVERZITNí 22, 306 14 PLZEŇ, CZECH REPUBLICSearch for more papers by this authorMartin Škoviera, Martin Škoviera DEPARTMENT OF COMPUTER SCIENCE, COMENIUS UNIVERSITY, MLYNSKÁ DOLINA, 842 48 BRATISLAVA, SLOVAKIASearch for more papers by this author Edita Máčajová, Edita Máčajová [email protected] DEPARTMENT OF COMPUTER SCIENCE, COMENIUS UNIVERSITY, MLYNSKÁ DOLINA, 842 48 BRATISLAVA, SLOVAKIASearch for more papers by this authorAndré Raspaud, André Raspaud [email protected] LABRI, UNIVERSITE DE BORDEAUX, 33405 TALENCE CEDEX, FRANCESearch for more papers by this authorEdita Rollová, Edita Rollová [email protected] NTIS - NEW TECHNOLOGIES FOR THE INFORMATION SOCIETY, UNIVERSITY OF WEST BOHEMIA, UNIVERZITNí 22, 306 14 PLZEŇ, CZECH REPUBLICSearch for more papers by this authorMartin Škoviera, Martin Škoviera DEPARTMENT OF COMPUTER SCIENCE, COMENIUS UNIVERSITY, MLYNSKÁ DOLINA, 842 48 BRATISLAVA, SLOVAKIASearch for more papers by this author First published: 11 March 2015 https://doi.org/10.1002/jgt.21866Citations: 12 Contract grant sponsor: EUROCORES Programme EUROGIGA; contract grant number: APVV-ESF-EC-0009-10; contract grant sponsor: Czech Science Foundation; contract grant sponsor: European Social Fund. Read the full textAboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Abstract We introduce the concept of a signed circuit cover of a signed graph. A signed circuit cover is a natural analog of a circuit cover of a graph and is equivalent to a covering of the corresponding signed graphic matroid with circuits. As in the case of graphs, a signed graph has a signed circuit cover only when it admits a nowhere-zero integer flow. In the present article, we establish the existence of a universal coefficient such that every signed graph G that admits a nowhere-zero integer flow has a signed circuit cover of total length at most . We show that if G is bridgeless, then , and in the general case . Citing Literature Volume81, Issue2February 2016Pages 120-133 RelatedInformation