On the structure and diameter of graph associahedra of graphs with a set of true twins

Abstract

The rotation distance between two search trees on a graph G is defined as the minimum number of rotations required to transform one tree into the other. A central problem in this context is to determine the maximum rotation distance between any pair of search trees on G, which corresponds to finding the diameter of the rotation graph R(G), or equivalently, the combinatorial diameter of the graph associahedron of G. in this article, we establish a relationship between the structure of R(G) and R(G-S) for a specific subset S of edges of G. More precisely, we show that if W is a set of true twins in G, and S consists of all edges in G with both endpoints in W, then R(G-S) is a quotient graph of R(G). Our main result provides a lower bound for diam R(G-S)) in terms of diam R(G). We apply this result to determine the diameter of rotation graphs of general windmill graphs. Furthermore, we improve the known bound for the diameter of graph associahedra of balanced complete bipartite graphs.