Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-03-26
Abstract： 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}}.$
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-03-26
Abstract： In 1975, P. Erd {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. In this paper, it is proved that $$f(n) geq n+ frac{107}{3}t+ frac{7}{3}$$
for $t=1260r+169 , (r geq 1)$
and $n geq frac{2119}{4}t^{2}+87978t+ frac{15957}{4}$. Consequently,
$ liminf sb {n to infty} {f(n)-n over sqrt n} geq sqrt {2 +
frac{7654}{19071}},$ which is better than the previous bounds
$ sqrt 2$ Y. Shi, Discrete Math. 71(1988), 57-71 , $ sqrt {2.4}$
C. Lai, Australas. J. Combin. 27(2003), 101-105 .
The conjecture $ lim_{n rightarrow infty} {f(n)-n over sqrt n}= sqrt {2.4}$ is not true.
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-03-26
Abstract： In 1975, P. Erd H os 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, cdots,c_n)$ is the cycle length distribution of a graph $G$ with $n$ vertices, where $c_i$ is the number of cycles of length $i$ in $G$. Let $f(a_1,a_2, cdots,$$a_n)$ denote the maximum possible number of edges in a graph which satisfies $c_i leq a_i$, where $a_i$ is a nonnegative integer. In 1991, Shi posed the problem of determining $f(a_1,a_2, cdots,a_n)，$ which extended the problem due to Erd H os. It is clear that $f(n)=f(1,1, cdots,1)$.Let $g(n,m)=f(a_1,a_2, cdots,a_n),$ where $a_i=1$ if $i/m$ is an integer, and $a_i=0$ otherwise.It is clear that $f(n)=g(n,1)$.We prove that $ liminf sb {n to infty} {f(n)-n over sqrt n} geq sqrt {2 + frac{40}{99}},$ which is better than the previous bounds $ sqrt 2$ (Shi, 1988), and $ sqrt {2 + frac{7654}{19071}}$ (Lai, 2017).We show that $ liminf_{n rightarrow infty} {g(n,m)-n over sqrt frac{n}{m}} > sqrt {2.444},$ for all even integers $m$. We make the following conjecture:$ liminf sb {n to infty} {f(n)-n over sqrt n} > sqrt {2.444}.$ par
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-02-18
Abstract： 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.$$
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-02-18
Abstract： 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)
Hits
YES
Hits
Downloads
Comment