Bipartite graphs with a perfect matching and digraphs

MaRDI QIDQ3392504zbMATH OpenFDO

Authors Zan-Bo Zhang, Dingjun Lou

Publication date 17 August 2009

Full work available at URL https://arxiv.org/abs/1011.4359, http://pphmj.com/abstract/4037.htm

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)

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.

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

Cited in

(4)

• Excluding a planar matching minor in bipartite graphs
• scientific article; zbMATH DE number 1555974 (Why is no real title available?)
• 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)