摘要
A.Ital和M.Rodeh给出了两个关于图的圈覆盖的猜想:(i)任意2-边连通图G=(V,E)有困覆盖C,使l(C)≤|E|+|V|-1;(n)任意2-边连通图有困覆盖,使图的每条边至多被覆盖两次.本文证明了猜想对平面图和2-边连通没有3-边割的图成立,并给出了一与两猜想等价的条件.同时也对著名的2-圈覆盖猜想作了讨论.
. Ital and M. Rodeh gave two conjectures about Cycle---- Covering: (i) every 2 edge connected graph has a cycle cover C. such that,; (ii) every 2-- edge connected graph has a cycle cover, with which every edge is covered at most twice. This paper proves that the conjectures are hold for planar graphs and 2--edgeconnected graphs without 3 -- edge cut and gives a condition equivalent to the conjectures. Meanwhile,this paper discusses the famous 2--Cycle Covering Conjecture.
出处
《青岛大学学报(自然科学版)》
CAS
1994年第1期44-48,共5页
Journal of Qingdao University(Natural Science Edition)
关键词
圈覆盖
欧拉子图
平面图
图论
ycle covering
Eulerian subgraph
planar graph