The maximum size of graphs with a unique k-factor

被引:0
作者
Volkmann, L [1 ]
机构
[1] Rhein Westfal TH Aachen, Lehrstuhl Math 2, D-52056 Aachen, Germany
关键词
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For suitable positive integers n and k let m(n, k) denote the maximum number of edges in a graph of order n which has a unique k-factor. In 1964, Hetyei and in 1984, Hendry proved m(n,1) = n(2)/4 for even n and m(n,2) = [n(n+1)/4], respectively. Recently, Johann confirmed the following conjectures of Hendry: m(n,k) = nk/2 + ((n-k)(2)) for k > n/2 and kn even and m(n,k) = n2/4 + (k-1)n/4 for n = 2kq, where q is a positive integer. In this paper we prove m(n,k) = k(2) + ((n-k)(2)) for n/3 less than or equal to k < n/2 and kn even, and we determine m(n, 3).
引用
收藏
页码:531 / 540
页数:10
相关论文
共 5 条
[1]   MAXIMUM GRAPHS WITH A UNIQUE K-FACTOR [J].
HENDRY, GRT .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1984, 37 (01) :53-63
[2]   A NOTE CONCERNING GRAPHS WITH UNIQUE F-FACTORS [J].
JACKSON, B ;
WHITTY, RW .
JOURNAL OF GRAPH THEORY, 1989, 13 (05) :577-580
[3]  
Johann P, 2000, J GRAPH THEOR, V35, P227, DOI 10.1002/1097-0118(200012)35:4<227::AID-JGT1>3.0.CO
[4]  
2-D
[5]   STRUCTURE OF FACTORIZABLE GRAPHS [J].
LOVASZ, L .
ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1972, 23 (1-2) :179-195