Bipartite graphs with a perfect matching and digraphs

zbMATH Open1189.05093arXiv1011.4359MaRDI QIDQ3392504FDOQ3392504

Authors: Zan-Bo Zhang, Dingjun Lou 

Publication date: 17 August 2009

Abstract: In this paper, we introduce a corresponding between bipartite graphs with a perfect matching and digraphs, which implicates an equivalent relation between the extendibility of bipartite graphs and the strongly connectivity of digraphs. Such an equivalent relation explains the similar results on $k$-extendable bipartite graphs and $k$-strong digraphs. We also study the relation among $k$-extendable bipartite graphs, $k$-strong digraphs and combinatorial matrices. For bipartite graphs that are not 1-extendable and digraphs that are not strong, we prove that the elementary components and strong components are counterparts.

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

Recommendations

• scientific article; zbMATH DE number 4066957
• scientific article; zbMATH DE number 6001476
• scientific article; zbMATH DE number 5926313
• Construction for bicritical graphs and \(k\)-extendable bipartite graphs
• scientific article; zbMATH DE number 5850547

zbMATH Keywords

digraphsirreducibleperfect matchingbipartite graphsindecomposableelementary component\(k\)-extendablestrong componentstrongly \(k\)-connected

Mathematics Subject Classification ID

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

Cited In (4)

• Excluding a planar matching minor in bipartite graphs
• Title not available (Why is that?)
• A note on generalized matching preclusion in bipartite graphs
• A notion of cross-perfect bipartite graphs

This page was built for publication: Bipartite graphs with a perfect matching and digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3392504)