Short signed circuit covers of signed graphs

Autor: Jing Chen, Genghua Fan
Rok vydání: 2018
Předmět:
Zdroj: Discrete Applied Mathematics. 235:51-58
ISSN: 0166-218X
DOI: 10.1016/j.dam.2017.10.002
Popis: A signed graph G is a graph associated with a mapping σ : E ( G ) → { + 1 , − 1 } . An edge e ∈ E ( G ) is positive if σ ( e ) = 1 and negative if σ ( e ) = − 1 . A circuit in G is balanced if it contains an even number of negative edges, and unbalanced otherwise. A barbell consists of two unbalanced circuits joined by a path. A signed circuit of G is either a balanced circuit or a barbell. A signed graph is coverable if each edge is contained in some signed circuit. An oriented signed graph (bidirected graph) has a nowhere-zero integer flow if and only if it is coverable. A signed circuit cover of G is a collection F of signed circuits in G such that each edge e ∈ E ( G ) is contained in at least one signed circuit of F ; The length of F is the sum of the lengths of the signed circuits in it. The minimum length of a signed circuit cover of G is denoted by s c c ( G ) . The first nontrivial bound on s c c ( G ) was established by Macajova et al., who proved that s c c ( G ) ≤ 11 | E ( G ) | for every coverable signed graph G , which was recently improved by Cheng et al. to s c c ( G ) ≤ 14 3 | E ( G ) | . In this paper, we prove that s c c ( G ) ≤ 25 6 | E ( G ) | for every coverable signed graph G .
Databáze: OpenAIRE
Externí odkaz: