Circuit k-covers of signed graphs
2021
Abstract Let G be a signed graph and F a set of signed circuits in G . For an edge e ∈ E ( G ) , F ( e ) denotes the number of signed circuits in F that contain e . F is called a circuit-cover of G if F ( e ) > 0 for each e ∈ E ( G ) , and a circuit k -cover of G if F ( e ) = k for each e ∈ E ( G ) . G is coverable if it has a circuit-cover. The existence of a circuit-cover in G is equivalent to the existence of a nowhere-zero flow in G . For a coverable signed graph G , it is proved in this paper that if each maximal 2-edge-connected subgraph of G is eulerian, then G has a circuit 6-cover, consisting of four circuit-covers of G , and as an immediate consequence, G has a circuit-cover of length at most 3 2 | E ( G ) | , generalizing a known result on signed eulerian graphs. New results on circuit k -covers are obtained and applied to estimating bounds on the lengths of shortest circuit-covers of signed graphs.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
12
References
0
Citations
NaN
KQI