分类: 数学 >> 离散数学和组合数学 提交时间: 2024-03-27
摘要: Let f(n) be the maximum number of edges in a graph on n vertices in which no two cycles have the same length. Erd¨os raised the problem of determining f(n). Erd¨os conjectured that there exists a positive constant c such that ex(n, C2k) ≥ cn1+1/k. Haj´os conjecture that every simple even graph on n vertices can be decomposed into at most n/2 cycles. We present the problems, conjectures related to these problems and we summarize the know results. We do not think Haj´os conjecture is true.
分类: 数学 >> 离散数学和组合数学 提交时间: 2024-03-26
摘要: In 1975, P. Erd {o}s proposed the problem of determining the maximum number $f(n)$ of edges in a graph of $n$ vertices in which any two cycles are of different lengths. In this paper, it is proved that $$f(n) geq n+32t-1$$ for $t=27720r+169 , (r geq 1)$ and $n geq frac{6911}{16}t^{2}+ frac{514441}{8}t- frac{3309665}{16}$. Consequently, $ liminf sb {n to infty} {f(n)-n over sqrt n} geq sqrt {2 + {2562 over 6911}}.$
分类: 数学 >> 离散数学和组合数学 提交时间: 2024-03-26
摘要: In 1975,P.Erd {o}sproposedtheproblemofdeterminingthemaximumnumber$f(n)$ofedgesinagraphwith$n$verticesinwhichanytwocyclesareofdifferentlengths.Inthispaper,itisprovedthat$$f(n) geqn+ frac{107}{3}t+ frac{7}{3}$$for$t=1260r+169 , (r geq1)$and$n geq frac{2119}{4}t^{2}+87978t+ frac{15957}{4}$.Consequently,$ liminf sb{n to infty}{f(n)-n over sqrtn} geq sqrt{2+ frac{7654}{19071}},$whichisbetterthanthepreviousbounds$ sqrt2$ Y.Shi,DiscreteMath.71(1988),57-71 ,$ sqrt{2.4}$ C.Lai,Australas.J.Combin.27(2003),101-105 .Theconjecture$ lim_{n rightarrow infty}{f(n)-n over sqrtn}= sqrt{2.4}$isnottrue.
分类: 数学 >> 离散数学和组合数学 提交时间: 2024-03-26
摘要: 设f(n) 是没有等长圈的n个顶点的图的最大可能边数。确定f(n)的问题由Erdos在1975年提出。本文给出了f(n)的下界。
分类: 数学 >> 离散数学和组合数学 提交时间: 2024-02-18
摘要: In 1975, P. Erdős proposed the problem of determining the maximum number $f(n)$ of edges in a graph on $n$ vertices in which any two cycles are of different lengths. Let $f^{\ast}(n)$ be the maximum number of edges in a simple graph on $n$ vertices in which any two cycles are of different lengths. Let $M_n$ be the set of simple graphs on $n$ vertices in which any two cycles are of different lengths and with the edges of $f^{\ast}(n)$. Let $mc(n)$ be the maximum cycle length for all $G \in M_n$. In this paper, it is proved that for $n$ sufficiently large, $mc(n)\leq \frac{15}{16}n$. We make the following conjecture: $$\lim_{n \rightarrow \infty} {mc(n)\over n}= 0.$$