摘要
图的圈基是图的一个重要结构 .一个圈基的长度是该圈基中所有圈的长度之和 .本文讨论了简单图的圈基长度的最大值 ,得到了如下结果 :设基圈数为 k,顶点数为 n的简单图的圈基长度最大值为 C* ,i)若 k≥ 4且 n≥ k +2时 ,C* =kn;ii)若 k =2 ,3,则对任意 n≥ 4 ,C* =kn- 1;iii)若 n(n≥ 5)为奇数 ,则对 k(k≥ 4 )的所有可能值 ,C* =kn.
The cycle basis of a graph is an important structure for a graph. The length of a cycle basis is the sum of the lengths of its cycles. In this paper the maximum value of the length of the cycle basis for simple graphs is discussed, and the follow results are obtained. Let C * be the maximum value of the length of the cycle basis for the simple graphs with basic cycle number k and vertex number n. i) If k≥4, then C *=kn for n≥k+2; ii) If k=2,3, then C *=kn-1 for any n≥4 ; iii) If n (n≥5) is odd, then C *=kn for any permissible k(k≥4).
出处
《数学研究》
CSCD
2000年第3期324-328,共5页
Journal of Mathematical Study
关键词
圈基长度
基圈数
最大值
简单图
Cycle basis, Length of a cycle basis, Basic cycle number, Maximum value
