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

详细信息    查看全文

• 作者：Zhiyong Gan ; Dingjun Lou ; Zanbo Zhang ; Xuelian Wen
• 关键词：Bipartite double cover ; perfect 2 ; matching covered graph ; 1 ; extendable graph ; minimally perfect 2 ; matching covered graph ; minimally 1 ; extendable graph ; algorithm ; 05C70
• 刊名：Frontiers of Mathematics in China
• 出版年：2015
• 出版时间：June 2015
• 年：2015
• 卷：10
• 期：3
• 页码：621-634
• 全文大小：168 KB
• 参考文献：1. Aho, A V, Hopcroft, J E, Ullman, J D (1976) The Design and Analysis of Computer Algorithms. Addison-Wesley Press, Reading
  2. Anunchuen, N, Caccetta, L (1994) On minimally k-extendable graphs. Australas J Combin 9: pp. 153-168
  3. Anunchuen, N, Caccetta, L (1997) Matching extension and minimum degree. Discrete Math 170: pp. 1-13 CrossRef
  4. Berge, C (1978) Regularizable graphs I. Discrete Math 23: pp. 85-89 CrossRef
  5. Berge, C (1981) Some common properties for regularizable graphs, edge-critical graphs, and B-graphs. Graph Theory and Algorithms. Lecture Notes in Comput Sci 108: pp. 108-123 CrossRef
  6. Hetyei, G (1964) Rectangular configurations which can be covered by 2 × 1 rectangles. Pécsi Tan F?isk K?zl 8: pp. 351-367
  7. Imrich, W, Pisanski, T (2008) Multiple Kronecker Covering Graphs. European J Combin 29: pp. 1116-1122 CrossRef
  8. Lou, D (1999) On the structure of minimally n-extendable bipartite graphs. Discrete Math 202: pp. 173-181 CrossRef
  9. Lovász, L, Plummer, M D (1986) Matching Theory. Elsevier Science, Amsterdam
  10. Micali, S, Vazirani, V V (1980) An $O(\sqrt n |E|)$ algorithm for finding maximum matching in general graphs. 21st Annual IEEE Symposium on Foundations of Computer Science, Syracuse, NY. pp. 17-27
  11. Plummer, M D (1980) On n-extendable graphs. Discrete Math 31: pp. 201-210 CrossRef
  12. Plummer, M D (1986) Matching extension in bipartite graphs. Proc 17th Southeastern Conf on Combinatorics, Graph Theory and Computing, Congress Numer 54, Utilitas Math Winnipeg. pp. 245-258
  13. Tutte, W T (1952) The factors of graphs. Canad J Math 4: pp. 314-328 CrossRef
  14. Waller, D A (1976) Double covers of graphs. Bull Aust Math Soc 14: pp. 233-248 CrossRef
  15. Zhou, S, Zhang, H (2009) Minimally 2-matching-covered graphs. Discrete Math 309: pp. 4270-4279 CrossRef
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Mathematics
  Chinese Library of Science
  
• 出版者：Higher Education Press, co-published with Springer-Verlag GmbH
• ISSN：1673-3576

文摘

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