Bipartite double cover and perfect 2-matching covered graph with its algorithm

Abstract

Let B(G) denote the bipartite double cover of a non-bipartite graph G with v≥2 vertices and ϵ edges. We prove that G is a perfect 2-matching covered graph if and only if B(G) is a 1-extendable graph. Furthermore, we prove that B(G) is a minimally 1-extendable graph if and only if G is a minimally perfect 2-matching covered graph and for each e = xy ∈ E(G), there is an independent set S in G such that |Γ_G(S)| = |S| + 1, x ∈S and |Γ_G-xy(S) | = |S|. Then, we construct a digraph D from B(G) or G and show that D is a strongly connected digraph if and only if G is a perfect 2-matching covered graph. So we design an algorithm in O(\sqrt{v}ϵ) time that determines whether G is a perfect 2-matching covered graph or not.

Keywords

Bipartite double cover / perfect 2-matching covered graph / 1-extendable graph / minimally perfect 2-matching covered graph / minimally 1-extendable graph / algorithm

References

[1] Aho A V, Hopcroft J E, Ullman J D. The Design and Analysis of Computer Algorithms. Reading: Addison-Wesley Press, 1976, 192-193

[2] Anunchuen N, Caccetta L. On minimally k-extendable graphs. Australas J Combin, 1994, 9: 153-168

[3] Anunchuen N, Caccetta L. Matching extension and minimum degree. Discrete Math, 1997, 170: 1-13

[4] Berge C. Regularizable graphs I. Discrete Math, 1978, 23: 85-89

[5] Berge C. Some common properties for regularizable graphs, edge-critical graphs, and B-graphs. In: Satio N, Nishzeki T, eds. Graph Theory and Algorithms. Lecture Notes in Comput Sci, 1981, 108: 108-123

[6] Hetyei G. Rectangular configurations which can be covered by 2 × 1 rectangles. Pécsi Tan Föisk Közl, 1964, 8: 351-367

[7] Imrich W, Pisanski T. Multiple Kronecker Covering Graphs. European J Combin, 2008, 29(5): 1116-1122

[8] Lou D. On the structure of minimally n-extendable bipartite graphs. Discrete Math, 1999, 202: 173-181

[9] Lovász L, Plummer M D. Matching Theory. Amsterdam: Elsevier Science, 1986

[10] Micali S, Vazirani V V. An O(n|E|) algorithm for finding maximum matching in general graphs. In: 21st Annual IEEE Symposium on Foundations of Computer Science, Syracuse, NY. 1980, 17-27

[11] Plummer M D. On n-extendable graphs. Discrete Math, 1980, 31: 201-210

[12] Plummer M D. Matching extension in bipartite graphs. In: Proc 17th Southeastern Conf on Combinatorics, Graph Theory and Computing, Congress Numer 54, Utilitas Math Winnipeg. 1986, 245-258

[13] Tutte W T. The factors of graphs. Canad J Math, 1952, 4: 314-328

[14] Waller D A. Double covers of graphs. Bull Aust Math Soc, 1976, 14: 233-248

[15] Zhou S, Zhang H. Minimally 2-matching-covered graphs. Discrete Math, 2009, 309: 4270-4279

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg