On degree sequences of undirected,directed, and bidirected graphs |
| |
Institution: | 1. Institut für Optimierung und Operations Research, Universität Ulm, Germany;2. Institut für Mathematik, Goethe-Universität Frankfurt, Frankfurt a.M., Germany |
| |
Abstract: | Bidirected graphs generalize directed and undirected graphs in that edges are oriented locally at every node. The natural notion of the degree of a node that takes into account (local) orientations is that of net-degree. In this paper, we extend the following four topics from (un)directed graphs to bidirected graphs: - –Erdős–Gallai-type results: characterization of net-degree sequences,
- –Havel–Hakimi-type results: complete sets of degree-preserving operations,
- –Extremal degree sequences: characterization of uniquely realizable sequences, and
- –Enumerative aspects: counting formulas for net-degree sequences.
To underline the similarities and differences to their (un)directed counterparts, we briefly survey the undirected setting and we give a thorough account for digraphs with an emphasis on the discrete geometry of degree sequences. In particular, we determine the tight and uniquely realizable degree sequences for directed graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|