Abstract: We generalize the class of split graphs to the directed case and show that these split digraphs can be identified from their degree sequences. The first degree sequence characterization is an extension of the concept of splittance to directed graphs, while the second characterization says a digraph is split if and only if its degree sequence satisfies one of the Fulkerson inequalities (which determine when an integer-pair sequence is digraphic) with equality.
Recommendations
Cites work
- scientific article; zbMATH DE number 3169205 (Why is no real title available?)
- scientific article; zbMATH DE number 3632548 (Why is no real title available?)
- A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs
- Algorithms for constructing graphs and digraphs with given valences and factors
- Decomposition of graphical sequences and unigraphs
- List Partitions
- Split graphs
- The splittance of a graph
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- The strong perfect graph theorem
- Threshold graphs and related topics
- Uniform sampling of digraphs with a fixed degree sequence
- Zero-one matrices with zero trace
Cited in
(14)- Oriented threshold graphs
- Results on the small quasi-kernel conjecture
- New classes of degree sequences with fast mixing swap Markov chain sampling
- Recognition of split-graphic sequences
- Comparability digraphs: an analogue of comparability graphs
- Split graphs
- Strict chordal digraphs viewed as graphs with distinguished edges
- Split graphs and block representations
- Unit and proper bitolerance digraphs
- Strong arc decompositions of split digraphs
- Split Hypergraphs
- Ends in digraphs
- Strict chordal and strict split digraphs
- Splitting digraphs
This page was built for publication: Split digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764900)
