Shorter signed circuit covers of graphs |
| |
| Authors: | Tomáš Kaiser Robert Lukot’ka Edita Máčajová Edita Rollová |
| |
| Affiliation: | 1. Department of Mathematics, University of West Bohemia, Plzen, Czech Republic;2. Department of Computer Science, Faculty of Mathematics, Physics and Informatics, Comenius University, Bratislava, Slovakia;3. Department of Computer Science, Comenius University, Faculty of Mathematics, Physics and Informatics, Bratislava, Slovakia;4. Department of Mathematics, Institute of Theoretical Computer Science, University of West Bohemia, Plzen, Czech Republic |
| |
| Abstract: | 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  edges can be covered by signed circuits of total length at most  , improving a recent result of Cheng et al. 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. |
| |
| Keywords: | short-circuit cover signed circuit signed graph |
|
|
