Source author record

Chunhui Lai

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

4works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2019arXiv

On the number of edges in some graphs

In 1975, P. Erdő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. The sequence $(c_1,c_2,\cdots,c_n)$ is the cycle length distribution of a graph $G$ of order $n$ 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ős, it is clear that $f(n)=f(1,1,\cdots,1)$ . Let $g(n,m)=f(a_1,a_2,\cdots,a_n),$ $a_i=1$ for all $i/m$ be integer, $a_i=0$ for all $i/m$ be not integer. It is clear that $f(n)=g(n,1)$ . We prove that $\liminf_{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), $\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_{n \to \infty} {f(n)-n \over \sqrt n} > \sqrt {2.444}.$

preprint2013arXiv

Some unsolved problems on cycles

Hajos' conjecture that every simple even graph on $n$ vertices can be decomposed into at most $(n-1)/2$ cycles (see L. Lovasz, On covering of graphs, in: P. Erdos, G.O.H. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 231 - 236). Let $f(n)$ be the maximum number of edges in a graph on $n$ vertices in which no two cycles have the same length. P. Erdos raised the problem of determining $f(n)$ (see J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, New York, 1976), p.247, Problem 11). Given a graph $H$ , what is the maximum number of edges of a graph with $n$ vertices not containing $H$ as a subgraph? This number is denoted $ex(n,H)$ , and is known as the Turan number. P. Erdos conjectured that there exists a positive constant $c$ such that $ex(n,C_{2k})\geq cn^{1+1/k}$ (see P. Erdos, Some unsolved problems in graph theory and combinatorial analysis, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), pp. 97--109, Academic Press, London, 1971). This paper summarizes some results on these problems and the conjectures that relate to these. We do not think Hajós conjecture is true.

preprint2010arXiv

On Potentially 3-regular graph graphic Sequences

For given a graph $H$ , a graphic sequence $π=(d_1,d_2,...,d_n)$ is said to be potentially $H$ -graphic if there exists a realization of $π$ containing $H$ as a subgraph. In this paper, we characterize the potentially $H$ -graphic sequences where $H$ denotes 3-regular graph with 6 vertices. In other words, we characterize the potentially $K_{3,3}$ and $K_6-C_6$ -graphic sequences where $K_{r,r}$ is an $r\times r$ complete bipartite graph. One of these characterizations implies a theorem due to Yin [25].

preprint2009arXiv

An Extremal Problem On Potentially $K_{r+1}-H$ -graphic Sequences

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 $σ(K_{m}-H, n)$ denote the smallest degree sum such that every $n$ -term graphical sequence $S$ with $σ(S)\geq σ(K_{m}-H, n)$ is potentially $K_{m}-H$ -graphical. In this paper, we determine the values of $σ(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 $σ(K_{r+1}-P_2, n)$ for $n\geq 4r+8, r\geq 3$ . There are a number of graphs on $k$ vertices which containing a tree on 4 vertices but not containing a cycle on 3 vertices (for example, the cycle on $k$ vertices, the tree on $k$ vertices, and the complete 2-partite graph on $k$ vertices, etc).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Chunhui Lai

Research overview

Is this your work?

4 publications

On the number of edges in some graphs

Some unsolved problems on cycles

On Potentially 3-regular graph graphic Sequences

An Extremal Problem On Potentially $K_{r+1}-H$ -graphic Sequences

See the researcher in context

Building this map preview

Chunhui Lai

Research overview

Is this your work?

4 publications

On the number of edges in some graphs

Some unsolved problems on cycles

On Potentially 3-regular graph graphic Sequences

An Extremal Problem On Potentially Kr+1−HK_{r+1}-HKr+1​−H-graphic Sequences

See the researcher in context

Building this map preview

An Extremal Problem On Potentially $K_{r+1}-H$ -graphic Sequences