Frontiers of Mathematics in China >
Bipartite double cover and perfect 2-matching covered graph with its algorithm
Received date: 03 Mar 2014
Accepted date: 07 Jan 2015
Published date: 01 Apr 2015
Copyright
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() time that determines whether G is a perfect 2-matching covered graph or not.
Zhiyong GAN , Dingjun LOU , Zanbo ZHANG , Xuelian WEN . Bipartite double cover and perfect 2-matching covered graph with its algorithm[J]. Frontiers of Mathematics in China, 2015 , 10(3) : 621 -634 . DOI: 10.1007/s11464-015-0449-z
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(
|
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
|
/
〈 | 〉 |