Let B（G） denote the bipartite double cover of a non-bipartite graph G with v ≥ 2 vertices and s edges. We prove that G is a perfect 2-matching covered graph if and only if B（G） is a 1-extendable graph. Furthermor...Let B（G） denote the bipartite double cover of a non-bipartite graph G with v ≥ 2 vertices and s 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 l-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（x√vε） time that determines whether G is a perfect 2-matching covered graph or not.展开更多
基金Acknowledgements The authors would like to thank the referees very much for their careful reading and their very instructive suggestions which improve this paper greatly. This work was supported in part by the National Natural Science Foundation of China （Grant No. 11201158）.
文摘Let B（G） denote the bipartite double cover of a non-bipartite graph G with v ≥ 2 vertices and s 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 l-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（x√vε） time that determines whether G is a perfect 2-matching covered graph or not.
