An end degree for digraphs

Matthias Hamann †, Karl Heuer · 2024

Read An end degree for digraphs by Matthias Hamann †, Karl Heuer (2024) 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-2412-01514.txt.

Introduction

Matthias Hamann and Karl Heuer define a new measure in a 2024 math paper on endless directed graphs. Ends of a graph are the ways a path can run off to infinity. Giving each end a degree, a count of how thick that escape is, was an open wish in the field.

Their definition is shown to be sound, which settles a problem raised by Zuther. An extended degree also counts the points that dominate the end. The main result sorts that extended degree by special chains of points that exhaust the end. The link mirrors a known one for plain graphs, though the directed case proves more complex.

Catalog record

CREATORMatthias Hamann †, Karl Heuer
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-01514

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An end degree for digraphs Thanks: † Funded by the Deutsche Forschungsgemeinschaft (DFG) - Project No. 549406527. Matthias Hamann †, Karl Heuer Abstract . In this paper we define a degree for ends of infinite digraphs. The well-definedness of our definition in particular resolves a problem by Zuther. Furthermore, we extend our notion of end degree to also respect, among others, the vertices dominating the end, which we denote as combined end degree. Our main result is a characterisation of the combined end degree in terms of certain sequences of vertices, which we call end-exhausting sequences. This establishes a similar, although more complex relationship as known for the combined end degree and end-defining sequences in undirected graphs. 2020 Mathematics Subject Classification 05C63, 05C20 1. Introduction The notion of ends became crucial for analysing the structure of infinite graphs. An end of a graph is an equivalence class of one-way infinite paths, where two such paths are called equivalent if they are joined by infinitely many disjoint paths. Degree parameters were defined for ends as well, see e.g. [ 2 , 7 ] , where the basic definition is as follows. The degree of an end \omega of a graph is the supremum (within \mathbb{N}\cup\{\infty\} ) of the number of disjoint one-way infinite paths in \omega . It is a non-trivial theorem by Halin [ 6 ] that the supremum in this definition is actually an attained maximum. End degrees turned out to be useful parameters for infinite graphs, e.g. for characterising a topological notion of infinite cycles [ 2 ] , or when studying extremal questions regarding the existence of infinite grid-like subgraphs [ 7 ] . A different way to describe the degree of an end is by certain sequences of nested finite vertex separators, so-called defining sequences . It was shown in [ 4 ] that one can characterise the degree of an end together with the number of vertices dominating it, also referred to as combined end degree , via the sizes of the separators within defining sequences. Here, a vertex v is said to dominate an end \omega if there exist infinitely many paths from v to a one-way infinite path in \omega which are all disjoint except from v . In this paper we shall consider directed graphs, briefly denoted as digraphs , which are infinite, and we shall define analogous concepts of end degrees as mentioned above for undirected graphs. For this we follow a notion of ends of digraphs defined by Zuther [ 8 , 9 ] , which is a natural and analog definition to the one for undirected graphs. An end of a digraph is defined as an equivalence class of rays and anti-rays, where a ( anti- ) ray is an orientation of a one-way infinite path such that each edge is oriented towards (resp. away from) infinity (see Section 2 for a precise definition). Zuther called two rays or anti-rays R_{1},R_{2} of a digraph D equivalent if there exist infinitely pairwise disjoint directed paths from R_{1} to R_{2} and vice versa. Note that this definition allows that e.g. R_{1} is a ray and R_{2} is an anti-ray. The first result of this paper, Theorem 3.1 , resolves a problem stated by Zuther [ 8 ] *Problem 2 and proves that an end of a digraph which contains any finite number of disjoint rays also contains infinitely many disjoint rays. Hence, Theorem 3.1 is an analogous result to the aforementioned theorem by Halin [ 6 ] , and allows us to define the in-degree (resp. out-degree ) of an end as the maximum number of disjoint rays (resp. anti-rays) in that end. The natural question arises whether an end with infinite in- and out-degree might admit a system of pairwise disjoint rays and anti-rays witnessing both of these degrees. By Theorem 4.1 we answer this question negatively and construct a digraph with infinite in- and out-degree where each ray intersects each anti-ray. The main contribution of this paper is the introduction of end-exhausting sequences , a concept for ends of digraphs similar to defining sequences for ends of undirected graphs. Similarly, although more complex as for undirected graphs, we define a combined in-degree (and out-degree ) for ends, and prove an equality to a parameter solely based on end-exhausting sequences in the following main result of this paper: Theorem 1.1 . Let D be a digraph and let \omega be an end of D that contains at least one but at most countably many rays. Then the combined in-degree of \omega is the same as \inf\left\{\liminf_{i\in\mathbb{N}}|U_{i}|\Bigm|(U_{i})_{i\in\mathbb{N}}\text{ is an }\omega\text{-exhausting sequence}\right\}, where both values are considered in \mathbb{N}\cup\{\infty\} . Qualitatively, Theorem 1.1 establishes the same duality between end-exhausting sequences and combined in-degrees (or out-degrees) of ends for digraphs as it is known for end-defining sequences and the combined end degree in the undirected case. The structure of this paper is as follows. After introducing some terminology in Section 2 , we prove in Section 3 that the in- and out-degree of an end is well-defined. In Section 4 we construct a digraph containing infinitely many disjoint rays and infinitely many disjoint anti-rays such that each ray intersects each anti-ray. In Section 5 we define end-exhausting sequences and the combined in- and out-degree of ends, followed by the proof of Theorem 1.1 . Finally, we briefly discuss in Section 6 how the results from Section 3 and Section 4 can be proved when edge-disjoint rays (and anti-rays) are considered instead of vertex-disjoint ones. 2. Preliminaries For general facts and notation regarding graphs we refer the reader to [ 3 ] , regarding digraphs in particular to [ 1 ] . We call a digraph D weak if it is weakly connected. For the sake of brevity we call a directed cycle just a dicycle and a directed path just a dipath . Given a dipath P containing two vertices a,b such that b is reached from a via P , we define aPb as the subdipath of P starting at a and ending in b . Given two vertex sets A , B , we call a dipath P an A – B dipath if P starts in A , ends in B and is internally disjoint from A\cup B . We call a weak digraph where each vertex has in- and out-degree 1 except one vertex v which has in-degree (resp. out-degree) 0 and out-degree (resp. in-degree) 1 a ray (resp. anti-ray ). The vertex v is called the starting vertex (resp. end vertex ) of the ray (resp. anti-ray). We say that a ray starts in a vertex set A if it has its starting vertex in A . Given a ray R with starting vertex v and some x\in V(R) we denote by Rx the subdipath vRx of R . A tail of R is a subray of R . If this tail starts at x , then we denote it by xR . Similarly, for an anti-ray Q with end vertex v and some x\in V(Q) , we denote by xQ the subdipath xQv of Q and by Qx the subanti-ray of Q that ends at x ,

Read the complete text