Xingzhi Zhan

Connected graphs with equal independence number and radius

Xingzhi Zhan

A classical theorem states that the independence number of any connected graph is at least its radius. In 2007, DeLaViña, Pepper, and Waller proved that every connected graph with…

A proof of Bickle's conjecture on collapsible graphs

Xingzhi Zhan

A graph $G$ is said to be $k$ -collapsible if $G$ has minimum degree $k$ and every non-null proper induced subgraph of $G$ has minimum degree less than $k .$ In 2018, Bickle conjectu…

Counterexamples to a conjecture of Hoa on maximal non-Hamiltonian graphs

Xingzhi Zhan

A graph G is said to be maximal non-Hamiltonian if G is non-Hamiltonian, but $G + e$ is Hamiltonian for every nonedge $e$ of $G .$ In 1994, Vu Dinh Hoa conjectured that if $C$ is a lo…

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…

The minimum number of detours in a connected graph of minimum degree three

Xining Liu, Pu Qiao, Xingzhi Zhan

A longest path in a graph is called a detour. Denote by $a (k, n)$ the minimum number of detours in a connected graph with minimum degree $k$ and order $n,$ and denote by $b (k, n)$ th…

Weakly pancyclic vertices in dense nonbipartite graphs

Yurui Tang, Xingzhi Zhan

Let $G$ be a graph of girth $g$ and circumference $c .$ A vertex $v$ of $G$ is called weakly pancyclic if $v$ lies on an $ℓ$ -cycle for every integer $ℓ$ with $g \leq ℓ \leq c .$ …

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…

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…

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…

Sparse graphs with an independent or foresty minimum vertex cut

Kun Cheng, Yurui Tang, Xingzhi Zhan

A connected graph is called fragile if it contains an independent vertex cut. In 2002 Chen and Yu proved that every connected graph of order $n$ and size at most $2 n - 4$ is fragile,…

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…

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…

math.CO2024★ 4 cited

A sufficient condition for pancyclic graphs

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 .$ We prove that every $2$ -connected $[4, 2]$ -graph of order at least $7$ is p…