Split digraphs

DOI10.1016/J.DISC.2011.12.023zbMATH Open1241.05116arXiv1005.2452OpenAlexW2912133305MaRDI QIDQ764900FDOQ764900

Authors: M. Drew LaMar 

Publication date: 16 March 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1005.2452

Recommendations

• Split Hypergraphs
• Split graphs
• Linear recognition of pseudo-split graphs
• Potentially graphic sequences of split graphs
• Splitting digraphs

zbMATH Keywords

split graphdegree sequenceFulkerson inequality

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Threshold graphs and related topics
• Title not available (Why is that?)
• The strong perfect graph theorem
• Title not available (Why is that?)
• Decomposition of graphical sequences and unigraphs
• Algorithms for constructing graphs and digraphs with given valences and factors
• The splittance of a graph
• List Partitions
• A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs
• Zero-one matrices with zero trace
• Split graphs
• The strong perfect graph conjecture: 40 years of attempts, and its resolution
• Uniform sampling of digraphs with a fixed degree sequence

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
• Split graphs and block representations
• Strict chordal digraphs viewed as graphs with distinguished edges
• 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)