Effects on the algebraic connectivity of weighted graphs under edge rotations

For a weighted graph G, the rotation of an edge uv(1) from v(1) to a vertex v(2) is defined as follows: delete the edge uv(1), set w(uv(2)) as w(uv(1))+w(uv(2)) if uv(2) is an edge of G; otherwise, add a new edge uv(2) and set w(uv(2))=w(uv(1)), where w(uv(1)) and w(uv(2)) are the weights of the edges uv(1) and uv(2), respectively. In this paper, effects on the algebraic connectivity of weighted graphs under edge rotations are studied. For a weighted graph, a sufficient condition for an edge rotation to reduce its algebraic connectivity and a necessary condition for an edge rotation to improve its algebraic connectivity are proposed based on Fiedler vectors of the graph. As applications, we show that, by using a series of edge rotations, a pair of pendent paths (a pendent tree) of a weighted graph can be transformed into one pendent path (pendent edges attached at a common vertex) of the graph with the algebraic connectivity decreasing (increasing) monotonically. These results extend previous findings of reducing the algebraic connectivity of unweighted graphs by using edge rotations. (c) 2024 Published by Elsevier Inc.