When all directed cycles have the same weight
Eli Berger, Daniel Carter, Paul Seymour · 2026
Read When all directed cycles have the same weight by Eli Berger, Daniel Carter, Paul Seymour (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-12746.txt.
Introduction
Eli Berger, Daniel Carter, and Paul Seymour characterize digraphs where every directed cycle can share one weight. A digraph is weightable if real weights on its edges make each directed cycle total one. That is a strong global condition linking all cycles at once. The team give several equivalent conditions for this property.
One version uses only zero and one weights with the same property. Another forbids a subdivided double cycle as a subdigraph. A third concerns triples of vertices and the cyclic order of cycles through them. Equivalent characterizations let researchers test weightability in many ways. The work sits in structural graph theory, a field Seymour helped shape.
Catalog record
| CREATOR | Eli Berger, Daniel Carter, Paul Seymour |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 118 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-12746
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
When all directed cycles have the same weight Eli Berger, Daniel Carter, Paul Seymour Abstract A digraph G G is weightable if its edges can be weighted with real numbers such that the total weight in each directed cycle equals 1. There are several equivalent conditions: that G G admits a 0 / 1 0/1 -weighting with the same property, or that G G contains no subdivided “double-cycle” as a subdigraph, or that for every triple of vertices, all directed cycles containing all three pass through them in the same cyclic order. And there is quite a rich supply of such digraphs: for instance, any digraph drawn in the plane such that each of its directed cycles rotates clockwise around the origin is weightable (let us call such digraphs “circular”), and there are weightable planar digraphs with much more complicated structure than this. Until now the general structure of weightable digraphs was not known, and that is our objective in this paper. We will show that: • there is a construction that builds every planar weightable digraph from circular digraphs; and • there is a (different) construction that builds every weightable digraph from planar ones. We derive a poly-time algorithm to test if a digraph is weightable. 1 Introduction Graphs and digraphs in this paper are finite, and may have loops or parallel edges. Let G be a digraph drawn in the plane (without crossings), where the origin belongs to one of the regions. Each edge e of G subtends an angle at the origin (a w(e) fraction of a full rotation, say). If the drawing has the property that w(e)>0 for every edge, then every directed cycle clearly must wind around the origin. But more than that; every directed cycle must wind around the origin exactly once, because curves that wind more than once intersect themselves. Let us call such a drawing circular . This is an intriguing property of digraphs. It is related to a theorem of Thomassen [ 5 , 9 ] , that says in one form: 1.1 . Let G be a digraph with no loops or parallel edges such that every vertex has in-degree and out-degree at least two, and suppose there are a,b\in V(G) such that every directed cycle contains at least one of a,b . Then there is no directed cycle containing both a,b if and only if G admits a circular drawing. This version of Thomassen’s result looks like it ought to be made somehow more general, and that brings us to the question that was the starting point of the research in this paper: is there a theorem that says “every appropriately connected digraph G contains no thing of type X if and only if G admits a circular drawing”? Let us say a weighting of a digraph G is a real-valued function w:E(G)\to\mathbb{R} , such that w(C)=1 for every directed cycle C , where w(C) means \sum_{e\in E(C)}w(e) , and if G admits a weighting, we say G is weightable . In a circular drawing, the function w defined earlier is a weighting, and so digraphs with circular drawings are weightable. For some time we hoped that for a converse, at least for sufficiently well-connected digraphs, that, say, every strongly 2-connected, weakly 3-connected weightable digraph admits a circular drawing (we will define these terms later). But this turns out to be false – see Figure 1 . Figure 1: A weightable digraph with no circular drawing. The four thick edges have weight one, and the others have weight zero. We still have not come up with the characterization we hoped for of the digraphs with circular drawings, but we now know which digraphs are weightable, and that is what we will explain in this paper. An answer to the question “which digraphs are weightable?” could mean several things: 1. A characterization of the minimal digraphs (under subdigraph containment) that are not weightable. 2. A poly-time algorithm to test whether an input digraph is weightable. 3. A poly-time algorithm to find a weighting if there is one. 4. A poly-time algorithm to test if a given function on E(G) is a weighting. 5. A method of construction that will build all (ond only) weightable digraphs by piecing together well-understood ones in prescribed ways. The first of these was already known [ 6 ] , but all the others are new and obtained in this paper. We will show in the next section that the third and fourth are both consequences of the second. The second is a consequence of the fifth, the construction method, which is our main theorem. We discuss this algorithm at the end of the paper. Curiously, the construction method breaks into two parts: roughly, we will show how to build all planar weightable digraphs, by piecing together those with circular embeddings; and then show how to build general weightable digraphs, by piecing together planar ones (with a different construction). Combining all of our constructions together yields the following theorem (we use some terms defined at the start of the next section): 1.2 . Let G be a 1-strong weightable digraph. Then at least one of the following is true: 1. G is not strongly 2-connected, and is obtained from two smaller 1-strong weightable digraphs by the construction described in 6.1 and depicted in Figure 5 . 2. G is not 3-weak, and is obtained from two smaller 1-strong weightable digraphs by the construction described in 6.2 and depicted in Figure 6 . 3. G is planar and admits a circular drawing. 4. G is planar, does not admit a circular drawing, and is obtained from two smaller 1-strong planar weightable digraphs by the construction described in 7.1 and depicted in Figure 7 . 5. G is nonplanar, and there is a subset Y\subseteq V(G) with |Y|\in\{3,4\} such that G\setminus Y has at least two weak components, and G is obtained from two or three smaller 1-strong weightable digraphs by one of the constructions described in 9.1 , 9.4 , or 9.5 and depicted in Figures 11 , 14 , or 15 , respectively. There is another way to describe the 1-strong planar weightable digraphs, as planar digraphs that admit a kind of tree-decomposition called a “bond carving” of “diwidth two”. This is discussed in Section 8 . 2 Preliminaries First, let us state some standard definitions. A graph G is k -connected if it has at least k+1 vertices and G\setminus X is connected for every X\subseteq V(G) with |X|<k . The underlying graph G^{-} of a digraph G is the graph obtained for forgetting the direction of all edges. A digraph is weakly connected if its underlying graph is connected, and weakly k -connected or k -weak if its underlying graph is k -connected. (We usually write “1-weak” for “weakly connected”.) A weak component of a digraph is a maximal 1-weak subdigraph. A dipath is a directed path, and a dicycle is a directed cycle. A digraph G is strongly connected if for every two vertices u,v there is a dipath from u to v . (This is equivalent to saying that G is 1-weak and every edge is in a dicycle.) A digraph G