分类: 数学 >> 离散数学和组合数学 提交时间: 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.$$
分类: 数学 >> 离散数学和组合数学 提交时间: 2024-02-18
摘要: Let $K_{m}-H$ be the graph obtained from $K_{m}$ by removing the edges set $E(H)$ of the graph $H$ ($H$ is a subgraph of $K_{m}$). We use the symbol $Z_4$ to denote $K_4-P_2.$ A sequence $S$ is potentially $K_{m}-H$-graphical if it has a realization containing a $K_{m}-H$ as a subgraph. Let $\sigma(K_{m}-H, n)$ denote the smallest degree sum such that every $n$-term graphical sequence $S$ with $\sigma(S)\geq \sigma(K_{m}-H, n)$ is potentially $K_{m}-H$-graphical. In this paper, we determine the values of $\sigma (K_{r+1}-U, n)$ for $n\geq 5r+18, r+1 \geq k \geq 7,$ $j \geq 6$ where $U$ is a graph on $k$ vertices and $j$ edges which contains a graph $K_3 \bigcup P_3$ but not contains a cycle on 4 vertices and not contains $Z_4$. There are a number of graphs on $k$ vertices and $j$ edges which contains a graph $(K_{3} \bigcup P_{3})$ but not contains a cycle on 4 vertices and not contains $Z_4$. (for example, $C_3\bigcup C_{i_1} \bigcup C_{i_2} \bigcup >... \bigcup C_{i_p}$ $(i_j\neq 4, j=2,3,..., p, i_1 \geq 5)$, $C_3\bigcup P_{i_1} \bigcup P_{i_2} \bigcup ... \bigcup P_{i_p}$ $(i_1 \geq 3)$, $C_3\bigcup P_{i_1} \bigcup C_{i_2} \bigcup >... \bigcup C_{i_p}$ $(i_j\neq 4, j=2,3,..., p, i_1 \geq 3)$, etc)