Changing the Uniform Spectrum by Deleting Edges

A graph is said to be k-uniformly connected if there exists a path of length k between each pair of vertices. This generalizes the well-known concept of a Hamiltonian-connected graph—a graph, order n, in which there exits a Hamiltonian path (path of length \(n-1\) ) between each pair of vertices. That is, a graph is Hamiltonian-connected if and only if it is \((n-1)\) -uniformly connected. One can also say a graph is complete if and only if it is 1-uniformly connected. The uniform spectrum of a graph G is the set of all k for which G is k-uniformly connected. In this chapter, we investigate the impact of adding or deleting vertices or edges on the uniform spectrum of a graph. Some general results are presented as well as analyses of specific classes of graphs such as bipartite graphs and wheels.