Graph Theory

A Nordhaus-Gaddum type problem for the normalized Laplacian spectrum and graph Cheeger constant

We prove a relationship between the isoperimetric number, Cheeger constant, and second-smallest eigenvalue of the normalized Laplacian of a graph

G

and its complement

G^{c}

J. Nolan Faught, Adam Knudson, Mark Kempton

Kemeny's constant for nonbacktracking random walks

We extend the definition of Kemeny’s constant to non-backtracking random walks and explore its relationship to the simple random walk.

Jane Breen, J. Nolan Faught, Cory Glover, Adam Knudson, Mark Kempton, Alice Oveson

A 1-separation formula for the graph Kemeny constant and Braess edges

We prove a new identity for Kemeny’s constant and provide sufficient conditions for an edge to be Braess in a general class of graphs.

J. Nolan Faught, Adam Knudson, Mark Kempton

Resistance Distance, Kirchhoff Index, and Kemeny's Constant in Flower Graphs

We obtain generalized formulas for the resistance distance and other graph metrics for a new class of graphs.

J. Nolan Faught, Adam Knudson, Mark Kempton