Abstract

Nordhaus-Gaddum type problems focus on bounding characteristics of graph and its complement. There are certain families of graphs which yield optimal upper bounds on various Nordhaus-Gaddum characteristics of graph. In this paper, we will talk about bounding combinatorial algebraic connectivity, normalized algebraic connectivity, the Cheeger constant, and the isoperimetric number of a graph and its complement. We will identify some optimal or near optimal families of graphs and conduct an analysis on these families that will help to bound these characteristics. We will also prove and conjecture some bounds that can help in formulating stronger bounds on these characteristics of graphs.

Degree

College and Department

Computational, Mathematical, and Physical Sciences; Mathematics

Rights

https://lib.byu.edu/about/copyright/