Title: Shorter signed circuit covers of graphs
Other Titles: Kratší pokrytí signovanými kružnicemi v grafech
Authors: Kaiser, Tomáš
Lukoťka, Robert
Máčajová, Edita
Rollová, Edita
Citation: KAISER, T., LUKOŤKA, R., MÁČAJOVÁ, E., ROLLOVÁ, E. Shorter signed circuit covers of graphs. Journal of Graph Theory, 2019, roč. 92, č. 1, s. 39-56. ISSN 0364-9024.
Issue Date: 2019
Document type: článek
URI: 2-s2.0-85058408444
ISSN: 0364-9024
Keywords in different language: short circuit cover;signed circuit;signed graph
Abstract in different language: A signed circuit is a minimal signed graph (with respect to inclusion) that admits a nowhere-zero flow. We show that each flow-admissible signed graph on m edges can be covered by signed circuits of total length at most (3+2/3)m, improving a recent result of Cheng et al. [manuscript, 2015]. To obtain this improvement we prove several results on signed circuit covers of trees of Eulerian graphs, which are connected signed graphs such that removing all bridges results in a collection of Eulerian graphs.
Rights: Plný text není přístupný.
© Wiley
Appears in Collections:Články / Articles (KMA)

Files in This Item:
File SizeFormat 
Kaiser_et_al-2019-Journal_of_Graph_Theory.pdf958,55 kBAdobe PDFView/Open    Request a copy

Please use this identifier to cite or link to this item: http://hdl.handle.net/11025/35177

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

  1. DSpace at University of West Bohemia
  2. Publikační činnost / Publications
  3. OBD