Professor Zhiyu Wang Discrete Math Seminar Talk

Title: Effective Resistance Curvature, Fractional Hamiltonicity, and Graph Toughness

Abstract: A graph is called resistance positive (RP) if it admits positive edge weights such that all vertex resistance curvatures are positive. A graph is fractionally Hamiltonian if it admits an edge weighting in $[0,1]$, of total weight equal to its order, such that every nontrivial edge cut has weight at least two. Motivated by Chv'atal's Toughness Conjecture, Scheinerman and Ullman conjectured that every $2$-tough graph is fractionally Hamiltonian, while Devriendt conjectured that every sufficiently tough graph is RP. In this talk, we discuss connections among effective resistance curvature, fractional Hamiltonicity, and graph toughness. In particular, we show that $1$-tough graphs need not be RP, whereas every $10$-tough graph is fractionally Hamiltonian and hence RP.