Sooyeong Kim

collaborators

3 papers

math.CO2024

A Nordhaus--Gaddum problem for the spectral gap of a graph

Sooyeong Kim, Neal Madras

Let $G$ be a graph on $n$ vertices, with complement $G$ . The spectral gap of the transition probability matrix of a random walk on $G$ is used to estimate how fast the r…

math.CO2023

Bounds on Kemeny's constant of a graph and the Nordhaus-Gaddum problem

Sooyeong Kim, Neal Madras, Ada Chan +3

We study Nordhaus-Gaddum problems for Kemeny's constant $K (G)$ of a connected graph $G$ . We prove bounds on $min {K (G), K (G)}$ and the pro…

math.CO2023

Kemeny's constant and enumerating Braess edges in trees

Jihyeug Jang, Mark Kempton, Sooyeong Kim +3

We study the problem of enumerating Braess edges for Kemeny's constant in trees. We obtain bounds and asympotic results for the number of Braess edges in some families of trees.