分类: 数学 >> 离散数学和组合数学 提交时间: 2022-10-24
摘要: Let f(n) be the maximum number of edges in a graph on n vertices in which no two cycles have the same length. Erdos raised the problem of determining f(n). Erdos conjectured that there exists a positive constant c such that ex(n, C2k) cn1+1/k. Hajos 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 Hajos conjecture is true.
分类: 数学 >> 离散数学和组合数学 提交时间: 2022-10-22
摘要: The set of all non-increasing nonnegative integers sequence = (d(v1), d(v2), ..., d(vn)) is denoted by NSn. A sequence NSn is said to be graphic if it is the degree sequence of a simple graph G on n vertices, and such a graph G is called a realization of . The set of all graphic sequences in NSn is denoted by GSn. A graphical sequence is potentially H-graphical if there is a realization of containing H as a subgraph, while is forcibly H-graphical if every realization of contains H as a subgraph. Let Kk denote a complete graph on k vertices. Let Km H be the graph obtained from Km by removing the edges set E(H) of the graph H (H is a subgraph of Km). This paper summarizes briefly some recent results on potentially Km G-graphic sequences and give a useful classification for determining (H, n).
分类: 数学 >> 离散数学和组合数学 提交时间: 2022-05-15
摘要: In 1975,P.Erd\{o}sproposedtheproblemofdeterminingthe maximumnumber$f(n)$ofedgesinagraphwith$n$verticesinwhich anytwocyclesareofdifferent lengths.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.
分类: 数学 >> 离散数学和组合数学 提交时间: 2022-05-14
摘要: 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}}.$
分类: 数学 >> 离散数学和组合数学 提交时间: 2022-05-10
摘要: 设f(n) 是没有等长圈的n个顶点的图的最大可能边数。确定f(n)的问题由Erdos在1975年提出。本文给出了f(n)的下界。