## Keywords

cycles, f(n), cycle, with, graph, that, Chunhui, which, Science, have, edges, Lai,, f(n)−, contains, Zhangzhou, Teachers, number, proved, vertex, College, exactly, consist, same, subgraph, vertices, lengths:, bound, distinct, maximum, this

## Transcript

Graphs without repeated cycle lengths

Chunhui Lai∗

Department of Mathematics

Zhangzhou Teachers College

Zhangzhou

Fujian 363000, P. R. of CHINA

and

Graph Theory and Combinatorics Laboratory

Institute of Systems Science

Academy of Mathematics and Systems Science

Chinese Academy of Sciences

Beijing 100080, P. R. of CHINA

zjlaichu@public.zzptt.fj.cn

Abstract

In 1975, Erdös proposed the problem of determining the maximum number f(n) of edges in a simple graph of n vertices in which any two cycles

are of different lengths. In this paper, it is proved that

f(n) ≥ n + 36t

for t = 1260r+169 (r ≥ 1) and n ≥ 540t2 + 175811

**2**
t+ 7989

**2**
. Consequently,

lim infn→∞

f(n)− n√

n

**≥**
**√**
**2 + 2**
**5**
**.**
1 Introduction

Let f(n) be the maximum number of edges in a graph on n vertices in which no two

cycles have the same length. In 1975, Erdös raised the problem of determining f(n)

(see [1], p. 247, Problem 11). Shi [2] proved that

f(n) ≥ n + [(√8n − 23 + 1)/2]

for n ≥ 3. Lai [3,4,5,6,7] proved that for n ≥ 6911

**16**
t2+ 514441

**8**
t− 3309665

**16**
, t = 27720r+169,

f(n) ≥ n + 32t − 1,

∗ Project supported by NSF of Fujian(A96026), Science and Technology Project of Fujian

(K20105) and Fujian Provincial Training Foundation for “Bai-Quan-Wan Talents Engineering”.

Australasian Journal of Combinatorics 27(2003), pp.101–105

and for n ≥ e2m(2m + 3)/4,

f(n) < n − 2 +

**√**
nln(4n/(2m + 3)) + 2n + log2(n + 6).

Boros, Caro, Füredi and Yuster [8] proved that

f(n) ≤ n + 1.98√n(1 + o(1)).

In this paper, we construct a simple graph G having no two cycles with the same

length which leads to the following result.

Theorem. Let t = 1260r + 169 (r ≥ 1); then

f(n) ≥ n + 36t

for n ≥ 540t2 + 175811

**2**
t + 7989

**2**
**.**
2 Proof of the theorem

Proof. Let t = 1260r+169, r ≥ 1, nt = 540t2 + 1758112 t+ 79892 , n ≥ nt. We shall show

that there exists a graph G on n vertices with n + 36t edges such that all cycles in

G have distinct lengths.

Now we construct the graph G which consists of a number of subgraphs: Bi,

(0 ≤ i ≤ 21t − 1, 27t ≤ i ≤ 28t + 64, 29t − 734 ≤ i ≤ 29t + 267, 30t − 531 ≤ i ≤

30t + 57, 31t − 741 ≤ i ≤ 31t + 58, 32t − 740 ≤ i ≤ 32t + 57, 33t − 741 ≤ i ≤

33t + 57, 34t − 741 ≤ i ≤ 34t + 52, 35t − 746 ≤ i ≤ 35t + 60, 36t − 738 ≤ i ≤

36t+ 60, 37t− 738 ≤ i ≤ 37t+ 799, i = 21t+ 2j + 1(0 ≤ j ≤ t− 1), i = 21t+ 2j(0 ≤

j ≤ t−1

**2**
), i = 23t + 2j + 1(0 ≤ j ≤ t−1

**2**
), and i = 26t).

Now we define these Bi. These subgraphs all have a common vertex x, otherwise

their vertex sets are pairwise disjoint.

For 0 ≤ i ≤ t − 1, let the subgraph B21t+2i+1 consist of a cycle

xu1i u

**2**
i . . . u

25t+2i−1

i x

and a path:

xu1i,1u

**2**
i,1 . . . u

(19t+2i−1)/2

i,1 u

(23t+2i+1)/2

i .

Based the construction, B21t+2i+1 contains exactly three cycles of lengths:

21t + 2i + 1, 23t + 2i, 25t + 2i.

For 0 ≤ i ≤ t−3

**2**
, let the subgraph B21t+2i consist of a cycle

xv1i v

**2**
i . . . v

25t+2i

i x

and a path:

**102**
xv1i,1v

**2**
i,1 . . . v

9t+i−1

i,1 v

12t+i

i .

Based the construction, B21t+2i contains exactly three cycles of lengths:

21t + 2i, 22t + 2i + 1, 25t + 2i + 1.

For 0 ≤ i ≤ t−3

**2**
, let the subgraph B23t+2i+1 consist of a cycle

xw1i w

**2**
i . . . w

26t+2i+1

i x

and a path:

xw1i,1w

**2**
i,1 . . . w

(21t+2i−1)/2

i,1 w

(25t+2i+1)/2

i .

Based the construction, B23t+2i+1 contains exactly three cycles of lengths:

23t + 2i + 1, 24t + 2i + 2, 26t + 2i + 2.

For 58 ≤ i ≤ t − 742, let the subgraph B27t+i−57 consist of a cycle

C27t+i−57 = xy1i y

**2**
i . . . y

132t+11i+893

i x

and ten paths sharing a common vertex x; the other end vertices are on the cycle

C27t+i−57:

xy1i,1y

**2**
i,1 . . . y

(17t−1)/2

i,1 y

**(37t−115)/2+i**
i xy1i,2y

**2**
i,2 . . . y

(19t−1)/2

i,2 y

**(57t−103)/2+2i**
i xy1i,3y

**2**
i,3 . . . y

(19t−1)/2

i,3 y

(77t+315)/2+3i

i xy1i,4y

**2**
i,4 . . . y

(21t−1)/2

i,4 y

(97t+313)/2+4i

i xy1i,5y

**2**
i,5 . . . y

(21t−1)/2

i,5 y

(117t+313)/2+5i

i xy1i,6y

**2**
i,6 . . . y

(23t−1)/2

i,6 y

(137t+311)/2+6i

i xy1i,7y

**2**
i,7 . . . y

(23t−1)/2

i,7 y

(157t+309)/2+7i

i xy1i,8y

**2**
i,8 . . . y

(25t−1)/2

i,8 y

(177t+297)/2+8i

i xy1i,9y

**2**
i,9 . . . y

(25t−1)/2

i,9 y

(197t+301)/2+9i

i xy1i,10y

**2**
i,10 . . . y

(27t−1)/2

i,10 y

(217t+305)/2+10i

i .

Since a cycle with d chords contains

**(**
d+2

**2**
**)**
distinct cycles, B27t+i−57 contains

exactly 66 cycles of lengths:

**103**
27t + i − 57, 28t + i + 7, 29t + i + 210, 30t + i,

31t + i + 1, 32t + i, 33t + i, 34t + i − 5,

35t + i + 3, 36t + i + 3, 37t + i + 742, 38t + 2i − 51,

38t + 2i + 216, 40t + 2i + 209, 40t + 2i, 42t + 2i,

42t + 2i − 1, 44t + 2i − 6, 44t + 2i − 3, 46t + 2i + 5,

46t + 2i + 744, 48t + 3i + 158, 49t + 3i + 215, 50t + 3i + 209,

51t + 3i − 1, 52t + 3i − 1, 53t + 3i − 7, 54t + 3i − 4,

55t + 3i − 1, 56t + 3i + 746, 59t + 4i + 157, 59t + 4i + 215,

61t + 4i + 208, 61t + 4i − 2, 63t + 4i − 7, 63t + 4i − 5,

65t + 4i − 2, 65t + 4i + 740, 69t + 5i + 157, 70t + 5i + 214,

71t + 5i + 207, 72t + 5i − 8, 73t + 5i − 5, 74t + 5i − 3,

75t + 5i + 739, 80t + 6i + 156, 80t + 6i + 213, 82t + 6i + 201,

82t + 6i − 6, 84t + 6i − 3, 84t + 6i + 738, 90t + 7i + 155,

91t + 7i + 207, 92t + 7i + 203, 93t + 7i − 4, 94t + 7i + 738,

101t + 8i + 149, 101t + 8i + 209, 103t + 8i + 205, 103t + 8i + 737,

111t + 9i + 151, 112t + 9i + 211, 113t + 9i + 946, 122t + 10i + 153,

122t + 10i + 952, 132t + 11i + 894.

B0 is a path with an end vertex x and length n − nt. Any other Bi is simply a

cycle of length i.

Then f(n) ≥ n + 36t, for n ≥ nt. This completes the proof.

From the above theorem, we have

lim inf

n→∞

f(n)− n√

n

**≥**
**√**
**2 +**
**2**
**5**
**,**
which is better than the previous bounds

**√**
2 (see [2]),

**√**
**2 + 2562**
**6911**
(see [7]).

Combining this with Boros, Caro, Füredi and Yuster’s upper bound, we get

1.98 ≥ lim sup

n→∞

f(n)− n√

n ≥ lim inf

n→∞

f(n)− n√

n

**≥**
**√**
**2.4.**
We make the following conjecture:

Conjecture.

lim

n→∞

f(n)− n√

n

**=**
**√**
**2.4.**
Acknowledgment

The author thanks Professors Yair Caro and Raphael Yuster for sending him reference

[8]. The author thanks Professors Genghua Fan and Cheng Zhao for their valuable

suggestions.

**104**
References

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan,

New York, 1976).

[2] Y. Shi, On maximum cycle-distributed graphs, Discrete Math. 71 (1988), 57–71.

[3] Chunhui Lai, On the Erdös problem, J. Zhangzhou Teachers College (Natural

Science Edition) 3(1) (1989), 55–59.

[4] Chunhui Lai, Upper bound and lower bound of f(n), J. Zhangzhou Teachers

College (Natural Science Edition) 4(1) (1990), 29, 30–34.

[5] Chunhui Lai, On the size of graphs with all cycle having distinct length, Discrete

Math. 122 (1993), 363–364.

[6] Chunhui Lai, The edges in a graph in which no two cycles have the same length,

J. Zhangzhou Teachers College (Natural Science Edition) 8(4) (1994), 30–34.

[7] Chunhui Lai, A lower bound for the number of edges in a graph containing no

two cycles of the same length, Electronic J. Combinatorics 8 (2001), #N9.

[8] E. Boros, Y. Caro, Z. Füredi and R. Yuster, Covering non-uniform hypergraphs

(submitted, 2000).

(Received 5/10/2001)

**105**