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

doi:10.1007/s11464-015-0449-z

Front. Math. China

2015, Vol. 10

Issue (3) : 621-634 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¹,Dingjun LOU^1,^*(

),Zanbo ZHANG²,Xuelian WEN³

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

Download: PDF(146 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

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

Corresponding Author(s): Dingjun LOU

Issue Date: 01 April 2015

Cite this article:

Zhiyong GAN,Dingjun LOU,Zanbo ZHANG, et al. Bipartite double cover and perfect 2-matching covered graph with its algorithm[J]. Front. Math. China, 2015, 10(3): 621-634.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-015-0449-z
https://academic.hep.com.cn/fmc/EN/Y2015/V10/I3/621

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 https://doi.org/10.1016/0012-365X(95)00352-W
4	Berge C. Regularizable graphs I. Discrete Math, 1978, 23: 85-89 https://doi.org/10.1016/0012-365X(78)90107-3
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 https://doi.org/10.1016/j.ejc.2007.07.001
8	Lou D. On the structure of minimally n-extendable bipartite graphs. Discrete Math, 1999, 202: 173-181 https://doi.org/10.1016/S0012-365X(98)00291-X
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 https://doi.org/10.1016/0012-365X(80)90037-0
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 https://doi.org/10.4153/CJM-1952-028-2
14	Waller D A. Double covers of graphs. Bull Aust Math Soc, 1976, 14: 233-248 https://doi.org/10.1017/S0004972700025053
15	Zhou S, Zhang H. Minimally 2-matching-covered graphs. Discrete Math, 2009, 309: 4270-4279 https://doi.org/10.1016/j.disc.2009.01.005

[1]	Mu-Fa CHEN, Yue-Shuang LI. Improved global algorithms for maximal eigenpair[J]. Front. Math. China, 2019, 14(6): 1077-1116.
[2]	Mu-Fa CHEN, Yue-Shuang LI. Development of powerful algorithm for maximal eigenpair[J]. Front. Math. China, 2019, 14(3): 493-519.
[3]	Xinzhen ZHANG, Guanglu ZHOU, Louis CACCETTA, Mohammed ALQAHTANI. Approximation algorith ms for nonnegative polynomial optimization problems over unit spheres[J]. Front. Math. China, 2017, 12(6): 1409-1426.
[4]	Mu-Fa CHEN. Global algorithms for maximal eigenpair[J]. Front. Math. China, 2017, 12(5): 1023-1043.
[5]	Guanli HUANG,Meng ZHOU. Termination of algorithm for computing relative Gr?bner bases and difference differential dimension polynomials[J]. Front. Math. China, 2015, 10(3): 635-648.
[6]	Kai ZHANG,Jiachuan ZHANG,Haibao DUAN,Jingzhi LI. Effective algorithms for computing triangular operator in Schubert calculus[J]. Front. Math. China, 2015, 10(1): 221-237.
[7]	Dongmei LI, Jinwang LIU, Weijun LIU. Normal projection: deterministic and probabilistic algorithms[J]. Front Math Chin, 2014, 9(1): 93-99.
[8]	Liping ZHANG. Linear convergence of an algorithm for largest singular value of a nonnegative rectangular tensor[J]. Front Math Chin, 2013, 8(1): 141-153.
[9]	Xing WANG, Dachuan XU, Xinyuan ZHAO. A primal-dual approximation algorithm for stochastic facility location problem with service installation costs[J]. Front Math Chin, 2011, 6(5): 957-964.
[10]	Junfeng LU, Zhenyue ZHANG. Convergence analysis of generalized nonlinear inexact Uzawa algorithm for stabilized saddle point problems[J]. Front Math Chin, 2011, 6(3): 473-492.
[11]	Yuning YANG, Qingzhi YANG. Singular values of nonnegative rectangular tensors[J]. Front Math Chin, 2011, 6(2): 363-378.
[12]	Xiaoling FU, Bingsheng HE, . Self-adaptive projection-based prediction-correction method for constrained variational inequalities[J]. Front. Math. China, 2010, 5(1): 3-21.
[13]	Weiping SHANG, Pengjun WAN, Xiaodong HU, . Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks[J]. Front. Math. China, 2010, 5(1): 75-87.
[14]	Vincent Y. B. Chen, William Y. C. Chen, Nancy S. S. Gu. The Abel lemma and the q-Gosper algorithm[J]. Front. Math. China, 2006, 1(4): 629-634.

Viewed

Full text

Abstract

Cited

Shared

Discussed