Songling Shan

activity

20242026

collaborators

Showing math.COShow all

8 papers · 1 filter

math.CO2026

Degree sequence condition for pancyclicity in tough graphs

Songling Shan, Zachary Warren

Let $t \geq 1$ be an integer, and let $G$ be a $t$ -tough $n$ -vertex graph with degree sequence $d_{1}, d_{2}, \dots, d_{n}$ in non-decreasing order. In 1995, Hoàng conjectured that if $G…

math.CO2026

Long Cycles in 2-Connected Tough Graphs

Songling Shan

Let $G$ be a graph. The circumference of $G$ , denoted by $c i r (G)$ , is the length of a longest cycle in $G$ , or zero if $G$ is acyclic. In 1993, Broersma, van den Heuvel, Jung, and…

math.CO2026

Non-Hamiltonian $\frac{3}{2}$ -Tough Plane Triangulations

Songling Shan

By Tutte's classic theorem of 1956 that every 4-connected planar graph is Hamiltonian, every planar graph of order at least three with toughness greater than $\frac{3}{2}$ is Hamil…

math.CO2026

Triangle-Free Graphs of Toughness Approaching Two Without a 2-Factor

Songling Shan

By work of Enomoto, Jackson, Katerinis, and Saito from 1985, every $2$ -tough graph has a $2$ -factor, and this toughness bound is best possible: for every $ε > 0$ , there exi…

math.CO2025

Hamilton cycles in tough $(2 P_{2} \cup P_{1})$ -free graphs

Songling Shan, Arthur Tanyel

In 1973, Chvátal conjectured that there exists a constant $t_{0}$ such that every $t_{0}$ -tough graph on at least three vertices is Hamiltonian. While this conjecture is still open, wo…

math.CO2025

Hamiltonian cycles in tough $(P_{4} \cup P_{1})$ -free graphs

Songling Shan

In 1973, Chvátal conjectured that there exists a constant $t_{0}$ such that every $t_{0}$ -tough graph on at least three vertices is Hamiltonian. This conjecture has inspired extensive…

math.CO2025

A strengthening of a degree sequence condition for Hamiltonicity in tough graphs

Songling Shan, Arthur Tanyel

Generalizing Chvátal's classic 1972 result, Hoàng proposed in 1995 the following conjecture, which strengthens Chvátal's result in terms of toughness: Let $t \geq 1$ be a positive in…

math.CO2024

Degree sequence condition for Hamiltonicity in tough graphs

Songling Shan, Arthur Tanyel

Generalizing both Dirac's condition and Ore's condition for Hamilton cycles, Chvátal in 1972 established a degree sequence condition for the existence of a Hamilton cycle in a grap…

Degree sequence condition for pancyclicity in tough graphs

Long Cycles in 2-Connected Tough Graphs

Non-Hamiltonian 23​-Tough Plane Triangulations

Triangle-Free Graphs of Toughness Approaching Two Without a 2-Factor

Hamilton cycles in tough (2P2​∪P1​)-free graphs

Hamiltonian cycles in tough (P4​∪P1​)-free graphs

A strengthening of a degree sequence condition for Hamiltonicity in tough graphs

Degree sequence condition for Hamiltonicity in tough graphs

Non-Hamiltonian $\frac{3}{2}$ -Tough Plane Triangulations

Hamilton cycles in tough $(2 P_{2} \cup P_{1})$ -free graphs

Hamiltonian cycles in tough $(P_{4} \cup P_{1})$ -free graphs