Coverings of Bipartite Graphs

1958/01/01 by A. L. Dulmage, N. S. Mendelsohn · 24 citations
Computer Science · #Advanced Graph Theory Research #Graph Theory and Algorithms

paper · pdf · doi:10.4153/cjm-1958-052-0

Abstract

For the purpose of analysing bipartite graphs (hereinafter called simply graphs) the concept of an exterior covering is introduced. In terms of this concept it is possible in a natural way to decompose any graph into two parts, an inadmissible part and a core. It is also possible to decompose the core into irreducible parts and thus obtain a canonical reduction of the graph. The concept of irreducibility is very easily and naturally expressed in terms of exterior coverings. The role of the inadmissible edges of a graph is to obstruct certain natural coverings of the graph.

Cited by

• Bargaining in a network of buyers and sellers
• b-invariant edges in essentially 4-edge-connected near-bipartite cubic bricks
• Nonbipartite Dulmage-Mendelsohn Decomposition for Berge Duality
• Dichotomy Results for Classified Rank-Maximal Matchings and Popular Matchings
• On Robust Popular Matchings with Tie-Bounded Preferences and Stable Matchings with Two-Sided Ties
• Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations
• Bipartite Graft I: Dulmage-Mendelsohn Decomposition for Combs
• Geometric Mesh Partitioning: Implementation and Experiments
• Facilitating Matches on Allocation Platforms
• Making Bipartite Graphs DM-irreducible
• Damping Effect on PageRank Distribution
• Matrices and α-Stable Bipartite Graphs
• The Exponential Hyper-Zagreb Indices and Structural Properties of Trees and Bipartite Graphs
• Residual Generation Using Physically-Based Grey-Box Recurrent Neural Networks For Engine Fault Diagnosis
• An Application of Manifold Learning in Global Shape Descriptors
• On the Equivalence of the Graph-Structural and Optimization-Based Characterizations of Popular Matchings
• Direction Matters: On Influence-Preserving Graph Summarization and Max-cut Principle for Directed Graphs
• Invariant systems of weighted representatives
• Design and Evaluation of a Structural Analysis-Based Fault Detection and Identification Scheme for a Hydraulic Torque Converter. [europepmc]
• Model-Based Fault Diagnosis of an Anti-Lock Braking System via Structural Analysis. [europepmc]
• A manifold-based approach to sparse global constraint satisfaction problems. [europepmc]
• Real-Time Detection of Incipient Inter-Turn Short Circuit and Sensor Faults in Permanent Magnet Synchronous Motor Drives Based on Generalized Likelihood Ratio Test and Structural Analysis. [europepmc]
• Greater white matter degeneration and lower structural connectivity in non-amnestic vs. amnestic Alzheimer's disease. [europepmc]
• Fault Detection and Isolation Based on Structural Analysis: Application to a Multi-Engine Propulsion Cluster. [europepmc]

Related

• The biparticity of a graph
• Graph covers and semi-covers: Who is stronger?
• Coverings of Profinite Graphs
• Three ways to cover a graph
• On bipartite coverings of graphs and multigraphs