摘要
In this paper we investigate cycle base structures of a （weighted） graph and show that much information of short cycles is contained in a MCB （minimum cycle base）. After setting up a Hall type theorem for base-transformation, we give a sufficient and necessary condition for a cycle base to be a MCB. Further more, we show that the structure of MCB in a （weighted） graph is unique. In the case of nonnegative weight, every pair of MCB have the same number of k-cycles for each integer k ≥ 3. The property is also true for those having longest length （although much work has been down in evaluating MCB, little is known for those having longest length）.
In this paper we investigate cycle base structures of a （weighted） graph and show that much information of short cycles is contained in a MCB （minimum cycle base）. After setting up a Hall type theorem for base-transformation, we give a sufficient and necessary condition for a cycle base to be a MCB. Further more, we show that the structure of MCB in a （weighted） graph is unique. In the case of nonnegative weight, every pair of MCB have the same number of k-cycles for each integer k ≥ 3. The property is also true for those having longest length （although much work has been down in evaluating MCB, little is known for those having longest length）.
基金
Supported by the National Natural Science Foundation of China(No.10271048,10671073)
Supported by Shanghai Leading Academic Discipline Project(No.B407)
Science and Technology Commission of Shanghai Municipality(No.07XD14011)
