Download Full Text - The Australasian Journal Of ...

Copy and paste this link to your website, so they can see this document directly without any plugins.



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

PDF Document reader online

This website is focused on providing document in readable format, online without need to install any type of software on your computer. If you are using thin client, or are not allowed to install document reader of particular type, this application may come in hand for you. Simply upload your document, and Docureader.top will transform it into readable format in a few seconds. Why choose Docureader.top?

  1. Unlimited sharing - you can upload document of any size. If we are able to convert it into readable format, you have it here - saved for later or immediate reading
  2. Cross-platform - no compromised when reading your document. We support most of modern browers without the need of installing any of external plugins. If your device can oper a browser - then you can read any document on it
  3. Simple uploading - no need to register. Just enter your email, title of document and select the file, we do the rest. Once the document is ready for you, you will receive automatic email from us.

Previous 10

Next 10