An official website of the United States government
Abstract In 1983, Bouchet conjectured that every flow‐admissible signed graph admits a nowhere‐zero 6‐flow. By Seymour's 6‐flow theorem, Bouchet's conjecture holds for signed graphs with all edges positive. Recently, Rollová et al proved that every flow‐admissible signed cubic graph with two negative edges admits a nowhere‐zero 7‐flow, and admits a nowhere‐zero 6‐flow if its underlying graph either contains a bridge, or is 3‐edge‐colorable, or is critical. In this paper, we improve and extend these results, and confirm Bouchet's conjecture for signed graphs with frustration number at most two, where the frustration number of a signed graph is the smallest number of vertices whose deletion leaves a balanced signed graph.
more »
« less
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
-
Let [Formula: see text] be a directed graph associated with a weight [Formula: see text]. For an edge-cut [Formula: see text] of [Formula: see text], the average weight of [Formula: see text] is denoted and defined as [Formula: see text]. An optimal edge-cut with average weight is an edge-cut [Formula: see text] such that [Formula: see text] is maximum among all edge-cuts (or minimum, symmetrically). In this paper, a polynomial algorithm for this problem is proposed for finding an optimal edge-cut in a rooted tree separating the root and the set of all leafs. This algorithm enables us to develop an automatic clustering method with more accurate detection of community output.more » « less
