On the number of edges in some graphs

Abstract: In 1975, P. ErdH{o}s proposed the problem of determining the maximum number

f (n)

of edges in a graph with

n

vertices in which any two cycles are of different lengths. The sequence

(c_{1}, c_{2}, c d o t s, c_{n})

is the cycle length distribution of a graph

G

of order

n

where

c_{i}

is the number of cycles of length

i

in

G

. Let

f (a_{1}, a_{2}, c d o t s, a_{n})

denote the maximum possible number of edges in a graph which satisfies

c_{i} l e q a_{i}

where

a_{i}

is a nonnegative integer. In 1991, Shi posed the problem of determining

f (a_{1}, a_{2}, c d o t s, a_{n})

which extended the problem due to ErdH{o}s, it is clear that

f (n) = f (1, 1, c d o t s, 1)

. Let

g (n, m) = f (a_{1}, a_{2}, c d o t s, a_{n}),

a_{i} = 1

for all

i / m

be integer,

a_{i} = 0

for all

i / m

be not integer. It is clear that

f (n) = g (n, 1)

. We prove that

l i m i n f_{n o i n f t y} f (n) - n o v e r s q r t n g e q s q r t 2 + f r a c 4099,

which is better than the previous bounds

s q r t 2

(Shi, 1988),

s q r t 2 + f r a c 765419071

(Lai, 2017). We show that

l i m i n f_{n i g h t a r r o w i n f t y} g (n, m) - n o v e r s q r t f r a c n m > s q r t 2.444,

for all even integers

m

. We make the following conjecture:

l i m i n f_{n o i n f t y} f (n) - n o v e r s q r t n > s q r t 2.444 .

Recommendations

Cites work

Cited in

(23)

This page was built for publication: On the number of edges in some graphs