Degree sequence condition for pancyclicity in tough graphs

Songling Shan; Zachary Warren

In the authors' words

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\`ang conjectured that if $G$ is Hamiltonian and, for every integer $i$ satisfying $t \leq i < n /2$ , $d_{i} \leq i$ , and $d_{n - i + t} < n - i$ , one has $d_{j} + d_{n - j + t} \geq n$ for all $j$ with $i < j < \frac{n}{2}$ , then $G$ is pancyclic or bipartite. In this paper, we disprove the conjecture for $t = 1$ and confirm it for all $t \geq 7$ .

Main resultLimitation the authors admit

Degree sequence condition for pancyclicity in tough graphs

In the authors' words

More on Combinatorics & discrete math that day

Circular s-choice parking functions: an exact closed formula via rotational symmetry

Single-Fragment Forensic Coding via Multidimensional Cyclically Permutable Codes

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

Proof of Almkvist's conjecture on the unimodality of partition polynomials

On infinite families of [Pn​]-irregular graphs

On infinite families of $[P_{n}]$ -irregular graphs