Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-03-27
Abstract： 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.
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-03-27
Abstract： 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).
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： Summary: "In this paper we consider a variation of the classical Turán-type extremal problems. Let $S$be an $n$-term graphical sequence, and $\sigma(S)$be the sum of the terms in $S$. Let $H$be a graph. The problem is to determine the smallest even $l$such that any $n$-term graphical sequence $S$having $\sigma(S)\geq l$has a realization containing $H$as a subgraph. Denote this value $l$by $\sigma(H,n)$. We show $\sigma(C_{2m+1},n)=m(2n-m-1)+2$, for $m\geq 3$, $n\geq 3m$; $\sigma(C_{2m+2},n)=m(2n-m-1)+4$, for $m\geq 3$, $n\geq 5m-2$.''
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)
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-02-13
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}-Z, n)$ for
$n\geq 5r+19, r+1 \geq k \geq 5,$ $j \geq 5$ where $Z$ is a graph on $k$
vertices and $j$ edges which
contains a graph $Z_4$ but
not contains a cycle on $4$ vertices. We also determine the values of
$\sigma (K_{r+1}-Z_4, n)$, $\sigma (K_{r+1}-(K_4-e), n)$,
$\sigma (K_{r+1}-K_4, n)$ for
$n\geq 5r+16, r\geq 4$.
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-02-13
Abstract： Let $K_k$, $C_k$, $T_k$, and $P_{k}$ denote a complete graph on $k$
vertices, a cycle on $k$ vertices, a tree on $k+1$ vertices, and a
path on $k+1$ vertices, respectively. 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}$). 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}-H, n)$ for
$n\geq 4r+10, r\geq 3, r+1 \geq k \geq 4$ where $H$ is a graph on $k$
vertices which
contains a tree on $4$ vertices but
not contains a cycle on $3$ vertices. We also determine the values of
$\sigma (K_{r+1}-P_2, n)$ for
$n\geq 4r+8, r\geq 3$.
Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-02-10
Abstract： "A sequence $S$is potentially $K_4-e$graphical if it has a realization containing a $K_4-e$as a subgraph. Let $\sigma(K_4-e,n)$denote the smallest degree sum such that every $n$-term graphical sequence $S$with $\sigma(S)\geq\sigma(K_4-e,n)$is potentially $K_4-e$graphical. Gould, Jacobson, Lehel raised the problem of determining the value of $\sigma(K_4-e,n)$. In this paper, we prove that $\sigma(K_4-e,n)=2[(3n-1)/2]$for $n\geq7$and $n=4,5$, and $\sigma(K_4-e,6)=20$.''
Hits
YES
Hits
Downloads
Comment