Frontiers of Mathematics in China >

2015 , Vol. 10 >Issue 3: 621 - 634

DOI: https://doi.org/10.1007/s11464-015-0449-z

RESEARCH ARTICLE

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

  • Zhiyong GAN 1 ,
  • Dingjun LOU , 1 ,
  • Zanbo ZHANG 2 ,
  • Xuelian WEN 3
Expand
  • 1. Department of Computer Science, Sun Yat-sen University, Guangzhou 510275, China
  • 2. Department of Computer Engineering, Guangdong Industry Technical College, Guangzhou 510300, China
  • 3. School of Economics and Management, South China Normal University, Guangzhou 510006, China

Received date: 03 Mar 2014

Accepted date: 07 Jan 2015

Published date: 01 Apr 2015

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg
Fold

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(vϵ) time that determines whether G is a perfect 2-matching covered graph or not.

Key words： Bipartite double cover; perfect 2-matching covered graph; 1-extendable graph; minimally perfect 2-matching covered graph; minimally 1-extendable graph; algorithm

Cite this article

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

References

Publishing order | Descend order by publishing year | Descend order by cited within
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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

Options
Outlines

/

〈 〉