Ruilin Zheng

collaborators

Showing math.COShow all

5 papers · 1 filter

math.CO2026

An asymptotically tight bound on oriented diameter

Yaojun Chen, Jifu Lin, Xiaolin Wang +1

Let $f (d)$ be the smallest integer such that every connected bridgeless graph of diameter $d$ admits an orientation with directed diameter at most $f (d)$ . Chvátal and Thomassen (19…

math.CO2026

The diameter of recoloring graphs under a maximum average degree bound

Ruilin Zheng, Junying Lu

For a graph $G$ , we write $mad (G)$ for its maximum average degree and $diam G$ for its diameter. Let $R_{k} (G)$ be the graph whose vertices are the proper colorings…

math.CO2026

Clique-saturating non-edges throughout the Turán range

Xiaolin Wang, Jiabao Yang, Ruilin Zheng

For an $F$ -free graph $G$ , a non-edge is $F$ -saturating if adding it to $G$ creates a copy of $F$ . We denote by $f_{p + 1} (n, m)$ the minimum number of $K_{p + 1}$ -saturating non-edges…

math.CO2026

Two-block cycles and chromatic number of Hamiltonian digraphs

Ruilin Zheng, Junying Lu, Xiaolin Wang +1

Let $k$ and $ℓ$ be positive integers. The family $C (k, ℓ)$ consists of all digraphs obtained from two internally vertex-disjoint directed paths of lengths at least $k$ and $\e…

math.CO2026

A note on long nontrivial cycle in Hamiltonian graphs

Xiaolin Wang, Jiabao Yang, Guangmiao Yu +1

Let $G$ be an $n$ -vertex graph containing a Hamiltonian cycle and with minimum degree at least $3$ . Girão, Kittipassorn and Narayanan (Israel J. Math., 2019) proved that $G$ contai…