Chengli Li

Nonhamiltonian regular sublinear expanders

Chengli Li, Yurui Tang

Letzter, Methuku and Sudakov proved that sufficiently regular sublinear expanders contain nearly spanning cycles and paths. Montgomery subsequently conjectured that every regular s…

Edge-disjoint Hamilton cycles under a bipartite-hole condition

Yanan Hu, Chengli Li, Feng Liu

In 2017, McDiarmid and Yolov introduced the bipartite-hole-number $α (G)$ and proved that $δ (G) \geq α (G)$ forces a Hamilton cycle. They also gave a sufficient con…

The number of cycles of a given length in dense hamiltonian graphs: proving Hilton's conjecture

Chengli Li, Leyou Xu, Bo Zhou

A classical theorem of Sheehan in 1977 states that every hamiltonian graph $G$ of order $n$ satisfying $e (G) > ⌊ \frac{n ^{2}}{4} ⌋ + 1$ contains at least two cycles…

The maximum number of paths of a given length in a nonhamiltonian graph

Chengli Li, Xingzhi Zhan

In 1980, Paul Erdős posed the following problem: For every positive integer $n,$ determine a nonhamiltonian graph of order $n$ having the maximum number of Hamilton paths. We solve…

Every $2$ -connected $[4, 2]$ -graph of order at least seven contains a pancyclic edge

Chengli Li, Xingzhi Zhan

A graph $G$ is called an $[s, t]$ -graph if any induced subgraph of $G$ of order $s$ has size at least $t .$ An edge $e$ in a graph $G$ of order $n$ is called pancyclic if for every i…

Cycles of consecutive lengths in $3$ -connected graphs

Chengli Li, Xingzhi Zhan

Recently Lin, Wang and Zhou have proved that every $3$ -connected nonbipartite graph of minimum degree at least $k$ with $k \geq 6$ and order at least $k + 2$ contains $k$ cycles of con…

Cycles and paths through vertices whose degrees are at least the bipartite-hole-number

Chengli Li, Feng Liu, Yurui Tang

The bipartite-hole-number of a graph $G$ , denoted by $α (G)$ , is the minimum integer $k$ such that there exist positive integers $s$ and $t$ with $s + t = k + 1$ , satisfyi…

The detour covering number and cummerbund covering number of a graph

Chengli Li, Xingzhi Zhan

We introduce several new concepts about graphs and investigate their basic properties. A longest path in a graph is called a detour and a longest cycle is called a cummerbund. The…

An Ore-type condition for hamiltonicity in graphs

Chengli Li, Feng Liu

The bipartite-hole-number of a graph $G$ , denoted as $α (G)$ , is the minimum number $k$ such that there exist positive integers $s$ and $t$ with $s + t = k + 1$ with the propert…

Cycles and paths through specified vertices in graphs with a given clique number

Chengli Li, Leyou Xu

B. Bollobás and G. Brightwell and independently R. Shi proved the existence of a cycle through all vertices whose degrees at least $\frac{n}{2}$ in any $2$ -connected graph of order…

The minimum size of a $k$ -connected locally nonforesty graph

Chengli Li, Yurui Tang, Xingzhi Zhan

A local subgraph of a graph is the subgraph induced by the neighborhood of a vertex. Thus a graph of order $n$ has $n$ local subgraphs. A graph $G$ is called locally nonforesty if…

Constructions of minimally $t$ -tough regular graphs

Kun Cheng, Chengli Li, Feng Liu

A non-complete graph $G$ is said to be $t$ -tough if for every vertex cut $S$ of $G$ , the ratio of $∣ S ∣$ to the number of components of $G - S$ is at least $t$ . The toughness $τ (G)$ o…

The minimum size of a $3$ -connected locally nonforesty graph

Chengli Li, Yurui Tang, Xingzhi Zhan

A local subgraph of a graph is the subgraph induced by the neighborhood of a vertex. Thus a graph of order $n$ has $n$ local subgraphs. A graph $G$ is called locally nonforesty if…

math.CO2024★ 1 cited

Longest cycles and longest chordless cycles in $2$ -connected graphs

Yanan Hu, Chengli Li, Feng Liu

Thomassen's chord conjecture from 1976 states that every longest cycle in a $3$ -connected graph has a chord. The circumference $c (G)$ and induced circumference $c^{'} (G)$ of a graph $…

The minimum size and maximum diameter of an edge-pancyclic graph of a given order

Chengli Li, Feng Liu, Xingzhi Zhan

A $k$ -cycle in a graph is a cycle of length $k .$ A graph $G$ of order $n$ is called edge-pancyclic if for every integer $k$ with $3 \leq k \leq n,$ every edge of $G$ lies in a $k$ -cycl…

Bound vertices of longest paths between two vertices in cubic graphs

Chengli Li, Feng Liu

Thomassen's chord conjecture from 1976 states that every longest cycle in a $3$ -connected graph has a chord. This is one of the most important unsolved problems in graph theory. Le…