Back to Search
Start Over
On degree sequences of undirected, directed, and bidirected graphs.
- Source :
-
European Journal of Combinatorics . Aug2017, Vol. 64, p113-124. 12p. - Publication Year :
- 2017
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ENUMERATIVE geometry
*DIRECTED graphs
*GRAPH theory
*BIJECTIONS
*GEOMETRIC vertices
Subjects
Details
- Language :
- English
- ISSN :
- 01956698
- Volume :
- 64
- Database :
- Academic Search Index
- Journal :
- European Journal of Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 123444019
- Full Text :
- https://doi.org/10.1016/j.ejc.2017.04.002